题目链接：http://noi.openjudge.cn/ch0111/06/
描述农夫约翰是一个精明的会计师。他意识到自己可能没有足够的钱来维持农场的运转了。他计算出并记录下了接下来 N (1 ≤ N ≤ 100,000) 天里每天需要的开销。
约翰打算为连续的M (1 ≤ M ≤ N) 个财政周期创建预算案，他把一个财政周期命名为fajo月。每个fajo月包含一天或连续的多天，每天被恰好包含在一个fajo月里。
约翰的目标是合理安排每个fajo月包含的天数，使得开销最多的fajo月的开销尽可能少。
接下来N行，每行包含一个1到10000之间的整数，按顺序给出接下来N天里每天的开销。输出一个整数，即最大月度开销的最小值。样例输入
7 5 100 400 300 100 500 101 400样例输出
500提示若约翰将前两天作为一个月，第三、四两天作为一个月，最后三天每天作为一个月，则最大月度开销为500。其他任何分配方案都会比这个值更大。
题目是中文题，因此题意很容易知道，数据太大，全部遍历会超时，二分很容易，但是要注意二分的条件，他可能会出错，我就是上面的判断里面return忽略了等于的情况。。。让电脑自己看着办了。。就一直错。。：
ac：
#include<stdio.h>
#include<string.h>
#include<math.h>
//#include<map>
#include<deque>
#include<queue>
#include<stack>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
#define da 0x3f3f3f3f
#define xiao -0x3f3f3f3f
#define clean(a,b) memset(a,b,sizeof(a))// 雷打不动的头文件
int shuzu[100100];
int r,l,n,m,mid,i,j,sum;
int judge()
{
i=0;
int num=0;
while(i<n)
{
sum=shuzu[i];
while(sum<=mid&&i<n)
{
i++;
sum=sum+shuzu[i];
}
num++;
if(num>m) //分的月份太多了，mid应该大一点
return 1; //这个mid太小了，应该大一点
}
//if(num<m) //分的月份太少了，mid应该小一点
return 0;
}
int main()
{
cin>>n>>m;
sum=0;
l=0;
for(i=0;i<n;++i)
{
cin>>shuzu[i];
sum=sum+shuzu[i];
l=l>shuzu[i]?l:shuzu[i]; //取最小的一个是左极限
}
r=sum;
//mid=(r+l)/2;
while(r>=l)
{
mid=(r+l)/2;
if(judge())
l=mid+1; //mid应该大一点 （左边向中间移动）
else
r=mid-1; //mid应该小一点（右边向中间移动）
}
cout<<mid<<endl;
}
京公网安备 11010502036488号