[TIOJ] 1562. Problem A 超級媽媽

題目連結:http://tioj.infor.org/problems/1562
本題跟骨牌遊戲有8成7像,只差在你一定要在最後一格也要有警報器響而已,所以就直接把警報器次數-1,然後就變一模一樣的骨牌遊戲了www
#include <stdio.h>
typedef long long lld;

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

int main(){
	while(scanf("%d %d",&n,&m)!=EOF){
		m--;
		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);
	}
}

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;
}

留言

這個網誌中的熱門文章

[TIOJ] 1271. [IOI 2012] Scrivener 斯克里夫尼

[TIOJ] 1429. [APIO '12] 忍者調度問題

[Codeforces] 731D. 80-th Level Archeology