题目连接：/contest/413975#problem/B

题目

农民约翰是一个令人震惊的会计巫师，他已经意识到他可能没有钱来经营这个农场。他已经计算并记录了确切的金额(1≤)。钱i≤10,000)他需要在下一天每天N(1≤)N≤100,000)天。

FJ想要为一个顺序的集合创建一个预算M(1≤)M≤N)被称为“fajomonths”的财政期。这些每个月都包含一组连续的1天或更多天。每一天都被限制在一个角落里。

FJ的目标是安排每个月的费用，以便最大限度地减少开支最高的人的开支，从而决定他每月的开支限额。

输入

第 1 行：两个空格分隔的整数：N和M

第 2 行..N+1：第i+1 行包含 Farmer John 在第i天花费的美元数

输出

第 1 行：Farmer John 能够承受的最小月度限额。 样本输入

7 5

100

400

300

100

500

101

400

样本输出

500

提示

如果 Farmer John 将月份安排为前两天（100和400）是一个月，第三和第四天（300和100）是一个月，最后三天（100、500和400）是他们自己的月份，那么他在任何一个月中最多花费 500 美元。任何其他调度方法都会提供更大的每月最低限额。

题意

给定一个数组，把他分成指定的部分，使得每部分金额的和最小时的最小金额。

思路

暴力模拟的话，就是利用已有的分割区块数，模拟出所有的情况对应的月度金额，记录求最小的。

二分就是反过来思考，随便给出一个合格的最低金额，得出所对应的区块数，判断他和给定的区块数的关系，最后二分逼近。两点核心1是二分解题的思想和代码实现2是确保最后结果，很多的细节，比如while(l<=r),if(a[i]-a[last]>mid),if(cnt>m)中的等于，return l;为什么返回的不是mid或r。

代码

#include <iostream>#include <algorithm>#include <string.h>#include <memory.h>using namespace std;const int M=100005;int n,m;int a[M];int f(int l,int r){///最小是a[i]中最大的，最大是a[i]的和while(l<=r){int cnt=1; ///cnt是最小为mid时，能分的区块数int mid=(l+r)/2;int last=0;for(int i=1;i<=n;i++){if(a[i]-a[last]>mid) ///a[i]一定<=mid,只判断前缀和与mid的关系{cnt++;last=i-1;}}///printf("最小为%d能分的区块数%d\n",mid,cnt);if(cnt>m) l=mid+1;else r=mid-1;///cnt==m说明mid需要更小}return l;}int main(){while(cin>>n>>m){int MAX=0;memset(a,0,sizeof(a));a[0]=0;for(int i=1;i<=n;i++){cin>>a[i];if(MAX<a[i])MAX=a[i];a[i]=a[i-1]+a[i]; ///前缀和，a[n]是a[i]的和}cout<<f(MAX,a[n])<<endl;}return 0;}