monthly expense(二分查找＋贪心).cpp

杭电acm解题报告2001---2099.

//贪心类似导弹防御系统
//朴素的就是从0->all全部枚举一遍
//能想到的优化就是二分查找了
#include <cstdio>
#include <string>

int n,m;
int value[101000],all;

char greedy(int monthv)
{
	int leftm, now, i;
	now = 0;
	leftm = m;
    for(i=0;i<n;i++) {
		if (now + value[i] <= monthv) {
			now += value[i];
		}
		else {
			now = 0;
			leftm --;
			i --;
		}
		if (leftm < 0) {
			return 'S';
		}
    }
	if (now <= monthv) {
		leftm --;
	}
    if (leftm == 0) {
		return 'E';
    }
	else if (leftm > 0) {
		return 'B';
	}
	return 'S';
}

int main()
{
	int i, minv;
	while (scanf("%d %d",&n,&m)==2) {
		all = 0;
		minv = 0x7fffffff;
		for (i=0;i<n;i++) {
			scanf("%d",&value[i]);
			all += value[i];
		}
		int l,r,mid;
		char state;
		l = 0;
		r = all;
		while (l < r) {
			mid = (l+r)/2;
			state = greedy(mid);
			if (state == 'B' || state == 'E') {//mid 可以的话，查找更小值
				r = mid;
			}
			else {//不可以的话，查找更大值
				l = mid+1;
			}
		}
		printf("%d\n",r);
	}
}