- Please go through the problem BOOKS1 Spoj. I figured out the following things and reached a state where I require your help:-
- I applied binary search over interval [max_element , sum_of_all_elements].
- then I calculate x = [lo + hi]/2 ;
- I check if I can partition the array in less than or equal to m parts such that no parts' sum is greater than x;
- If I successfully completed this task I reduce hi to x and carry on;
- The problem I face is there can be a case where I might not need exact k partitions (less than k might do) and output format such that first scriber's work is least
int main(){
int n;
cin>>n;
while(n--){
int m,k;
cin>>m>>k;
int a[501];
int s=0;
rep(i,m){
cin>>a[i];
s+=a[i];
}
int lo = *max_element(a,a+m);
int hi = s;
int it=100;
int req;
while(lo <= hi and it--){
int mid = lo + (hi-lo)/2;
int sum=0;
req=1;
for(int i=0;i<m;i++){
if(sum + a[i] <= mid){
sum += a[i];
trace1(sum);
}
else{
++req;
sum = a[i];
v.pb(i);
}
}
if(req<=k){
hi=mid;
}
else{
lo= mid+1;
}
}
// cout<<"loop terminated";
}
}
can you suggest me how can proceed further from here?