[TIOJ] 1432. 骨牌遊戲

題目連結:http://tioj.infor.org/problems/1432

---

本題直接二分搜答案吧，值得注意的是最初始的上界顯然是數列和，但下界要注意的是它是數列中的最大值-1，因為顯然小於最大值-1的數一定會讓他壞掉，然後驗證二分搜就直接跑過去算，大概醬吧XD

#include <stdio.h>
typedef long long lld;

int n,m;
lld arr[1000 + 10];
inline bool test(lld);

int main(){
	scanf("%d %d",&n,&m);
	while(n!=0 || m!=0){
		lld l=0,r=0;
		for(int i=0;i<n;i++){
			scanf("%lld",&arr[i]);
			r+=(lld)arr[i];
			l=(l>arr[i])?l:arr[i];
		}
		l-=1;
		while(r-l != 1){
			if(test((r+l)/2))
				r=(r+l)/2;
			else
				l=(r+l)/2;
		}
		printf("%lld\n",r);
		scanf("%d %d",&n,&m);
	}
}

inline bool test(lld maxS){
	int k=0;
	lld plus=0;
	for(int i=0;i<n;i++){
		if(plus + arr[i] > maxS){
			plus=arr[i];
			k++;
			if(k>m) return 0;
		}else
			plus+=arr[i];
	}
	return 1;
}