hulk_baba's blog

By hulk_baba, 7 years ago, In English
  1. Please go through the problem BOOKS1 Spoj. I figured out the following things and reached a state where I require your help:-
  2. I applied binary search over interval [max_element , sum_of_all_elements].
  3. then I calculate x = [lo + hi]/2 ;
  4. 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;
  5. If I successfully completed this task I reduce hi to x and carry on;
  6. 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?

  • Vote: I like it
  • -17
  • Vote: I do not like it

| Write comment?