faseterjob.java

《算法设计与分析》王晓东编著

public class FaseterJob {
	
	public static int fasterJob(int[] d,int[] w,int[] job)
	{
		int n=d.length-1;
		int[] f=new int[n+1];
		for (int i=0;i<=n;i++) f[i]=i;
		FastUnionFind U=new FastUnionFind(n);
		int k=0,t=0;
		for (int i=1;i<=n;i++) {
			int m=(n<d[i])?U.find(n):U.find(d[i]);
			if (f[m]>0) {
				k=k+1;
				job[k]=i;
				if (f[m]>1) {
					t=U.find(f[m]-1);
					U.union(t,m);
				}				
				else t=0;
				f[m]=f[t];
			}				
		}
		for (int i=1;i<=k;i++)
			w[job[i]]=0;
		int sum=0;
		for (int i=1;i<=n;i++)
			if (w[i]>0) {
				job[++k]=i;
				sum+=w[i];
			}
		return sum;
	}
	
	public static void main(String args[])
	{
		int d[]=new int[]{0,4,2,4,3,1,4,6};
		int w[]=new int[]{0,70,60,50,40,30,20,10};
		int job[]=new int[d.length];
		
		System.out.println(fasterJob(d,w,job));
	}
}