题目大意：
共N ( 1 ≤ N ≤ 100,000 )个 工作日 ，分M ( 1 ≤ M ≤ N ) 个 清算月
一个 清算月 包含一个工作日或更多连续的工作日，每一个工作日都仅被包含在一个 清算月 当中。
按顺序分组，得到一个最大值最小化的月度开支（即 在 所有可能的分组结果的最大值 中得到一个最小的）
Input
Line 1: Two space-separated integers: N and M
Lines 2..N+1: Line i+1 contains the number of dollars Farmer John spends on the i-th day
Output
Line 1: The smallest possible monthly limit Farmer John can afford to live with.
Sample Input
7 5
100
400
300
100
500
101
400
Sample Output
500
Hint
If Farmer John schedules the months so that the first two days are a month, the third and fourth are a month, and the last three are their own months, he spends at most $500 in any month. Any other method of scheduling gives a larger minimum monthly limit.
思路来自：http://hzwer.com/2661.html
#include <bits/stdc++.h>
using namespace std;
int n,m,ans,a[];
int judge(int mid)
{
int sum=,cnt=;
for(int i=;i<=n;i++)
{
if(sum+a[i]<=mid) sum+=a[i];
/// 连加 分为一组 直到该组总和大于mid
else
{
sum=a[i]; cnt++; ///cnt记下组数 sum从a[i]开始重新连加
if(cnt>m || sum>mid) return ;
/// 若组数超过m 或 有比mid更大的花费 返回0
}
}
return ;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++) scanf("%d",&a[i]);
int le=,rig=;
while(le<=rig) ///不断缩小范围直到找到答案
{
int mid=(le+rig)>>;
///取中值 mid小了就le=mid+1向右找 否则就rig=mid-1向左找
if(judge(mid)) /// 若返回1 mid>=答案
{
ans=mid; /// 先保存mid
rig=mid-;
///若此时mid=答案 而rig=mid-1了 继续循环在judge()时只会进入else部分直到跳出循环。否则mid大了 继续缩小直到得到mid=答案。
}
else le=mid+; /// 若返回0 则花费中有比mid更大的 mid小了
}
printf("%d\n",ans); return ;
}
在一场比赛时用了这个方法，一直超时，其实可以在左右值上加个小优化
#include <bits/stdc++.h>
using namespace std;
int n,m,ans,a[];
int judge(int mid)
{
int sum=,cnt=;
for(int i=;i<=n;i++)
{
if(sum+a[i]<=mid) sum+=a[i];
/// 连加 分为一组 直到该组总和大于mid
else
{
sum=a[i]; cnt++; ///cnt记下组数 sum从a[i]开始重新连加
if(cnt>m || sum>mid) return ;
/// 若组数超过m 或 有比mid更大的花费 返回0
}
}
return ;
}
int main()
{
scanf("%d%d",&n,&m);
int le=,rig=;
for(int i=;i<=n;i++){
scanf("%d",&a[i]);
le=min(le,a[i]);
rig+=a[i];
}
while(le<=rig) ///不断缩小范围直到找到答案
{
int mid=(le+rig)>>;
///取中值 mid小了就le=mid+1向右找 否则就rig=mid-1向左找
if(judge(mid)) /// 若返回1 mid>=答案
{
ans=mid; /// 先保存mid
rig=mid-;
///若此时mid=答案 而rig=mid-1了 继续循环在judge()时只会进入else部分直到跳出循环。否则mid大了 继续缩小直到得到mid=答案。
}
else le=mid+; /// 若返回0 则花费中有比mid更大的 mid小了
}
printf("%d\n",ans); return ;
}