典型的二分，二分上限是组成一个组，花费是每月花费之和，下线是组成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;

　　}

　　}