POJ 3273 Monthly Expense（最大值最小化）

题目链接：点击这里

#include<iostream>
#include<algorithm>
#include<string>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<stack>
#include<queue>
#include<map>
#include<set>

using namespace std;
typedef long long ll;
const int MOD = 10000007;
const int INF = 0x3f3f3f3f;
const double PI = acos(-1.0);
const int maxn =  100010;
int a[maxn];
int n, m;

bool check(int mid)
{
	int cnt = 0, sum = 0;
	for(int i = 1; i <= n; i++)
	{
		if(sum+a[i]>mid)
		{
			cnt++;
			if(a[i]>mid)	return false;
			sum = a[i];
		}
		else
		{
			sum += a[i];
		}
	}
	return cnt < m;
}

int main()
{
	scanf("%d%d", &n, &m);
	int sum = 0;
	for(int i = 1; i <= n; i++)
	{
		scanf("%d", &a[i]);
		sum += a[i];
	}
	
	int left = 0, right = sum, ans;
	while(left <= right)
	{
		int mid = left+(right-left)/2;	//二分
		if(check(mid))
		{
			ans = mid;		//记录答案
			right = mid - 1;	//移动right
		}
		else
		{
			left = mid + 1;		//移动left
		}
	}
	printf("%d\n", ans);
	return 0;
}