TIOJ 1432 骨牌遊戲 [Binary Search]

poao899    4K    15MS    G++     0.53K     2009-11-19 22:55:22                                 .

純粹為了練coding速度(咦

對答案二分搜。

//***********************

#include<stdio.h>
int n,w,s[1000000],val;
bool test(int max){
	int cost=0,sum=0;
	for(int i=0;i<n;i++){
		sum+=s[i];
		if(sum>max){
			sum=s[i];
			cost++;
			if(cost>w)return 0;
		}
	}
	return 1;
}
main(){
	while(scanf("%d%d",&n,&w),n+w){
		int l=0,r=0;
		for(int i=0;i<n;i++){
			scanf("%d",s+i);
			if(s[i]>l)l=s[i];
			r+=s[i];
		}
		while(l!=r){
			int mid=(l+r)/2;
			if(!test(mid))
				l=mid+1;
			else r=mid;
		}
		printf("%d\n",l);
	}
}