GitBook

这里写图片描述 这里写图片描述

二分法 答案符合的条件是让 可以分的月数不大于m

注意一旦有单一元素超过x 则x肯定不是解

#include<stdio.h>
int a[100200];
int n,m;
bool judge(int x) {
	int sum=0,cnt=1;
	for(int i=0; i<n; i++) {
		if(a[i]>x)
			return false;
		sum+=a[i];
		if(sum>x) {
			cnt++;
			sum=a[i];
		}
	}
	if(cnt>m)
		return false;
	else
		return true;
}
int main() {
	while(scanf("%d %d",&n,&m)!=EOF) {
		int l=0,r=0;
		for(int i=0; i<n; i++) {
			scanf("%d",&a[i]);
			r+=a[i];
		}
		int mid,res;
		while(r>=l) {
			mid=(l+r)/2;
			if(judge(mid)) {
				res=mid;
				r=mid-1;
			} else
				l=mid+1;
		}
		printf("%d\n",res);
	}
	return 0;
}

题目地址:【POJ】[3273]Monthly Expense