poj3273

典型的二分，二分上限是組成一個組，花費是每月花費之和，下線是組成N個組，花費是他們中最大的。單調性容易證明，分成組越少，花費越高，分成組越多，花費越少，呈線性關系，故可以采用二分法求解單調函數極值（最值）。

#include 
#include 

using namespace std;

bool judge(int N, int M, int mid, vector  a) {
	int sum = 0;
	int group = 1;
	for (int i = 0; i < N; i++) {
		if (sum + a[i] <= mid) {                             // sum from day 0 to day i, if the sum <= mid, it means they must be in one group
			sum += a[i];
		}
		else { // if sum from day 0 to day i-1, plus day i, is bigger than sum, then it should be divided in to two groups, day 1 to day i-1, day i.
			sum = a[i];
			group++;
		}
	}
	if (group > M) {
		return false;
	}
	else return true;
}

int main() {
	int N, M;
	vector  a;
	while (cin >> N >> M) {
		int max = 0, sum = 0;
		for (int i = 0; i < N; i++) { //max group->n group->with max upon money, min group->1 group with sum of money
			int temp;
			cin >> temp;
			a.push_back(temp);
			if (temp > max) {
				max = temp;
			}
			sum += temp;
		}
        
		int mid = (max + sum) >> 1;
		while (max < sum) {
			if (judge(N, M, mid, a)) {
				sum = mid - 1;
			}
			else max = mid + 1;
			mid = (sum + max) >> 1;
		}
		cout << mid << endl;
	}
}