Create a gist now

Instantly share code, notes, and snippets.

FairWorkload - SRM 169
public class FairWorkload {
public static void main(String[] args){
FairWorkload workload = new FairWorkload();
System.out.println(workload.getMostWork(new int[]{10,20,30,40,50,60,70,80,90},3));
System.out.println(workload.getMostWork(new int[]{10,20,30,40,50,60,70,80,90},5));
System.out.println(workload.getMostWork(new int[]{568, 712, 412, 231, 241, 393, 865, 287, 128, 457, 238, 98, 980, 23, 782},4));
System.out.println(workload.getMostWork(new int[]{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1000},2));
System.out.println(workload.getMostWork(new int[]{50, 50, 50, 50, 50, 50, 50 },2));
System.out.println(workload.getMostWork(new int[]{1,1,1,1,100},5));
System.out.println(workload.getMostWork(new int[]{950, 650, 250, 250, 350, 100, 650, 150, 150, 700},6));
}
int getMostWork(int[] folders, int workers){
int low = 0;
int high= 0;
//low=1<<30;
for(int f: folders){
//if(f<low){ low=f; } // XXX
if(low<f){ low=f; } // XXX
high+=f;
}
int mid=0, c=0, t=0, m=0;
while(low<high){
mid = low + (high-low)/2;
System.out.printf("%d,%d,%d\n",low,mid,high);
c=t=0;
for(int f: folders){
if(mid<f){ break; }
if(t+f<=mid){t+=f; }
else{
t=f; c++;
}
}
if(c<workers){ high = mid; }
else{ low = mid+1; }
System.out.printf("c=%d,m=%d\n",c,m);
}
return low;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment