描述

有n个正整数排成一排，你要将这些数分成m份（同一份中的数字都是连续的，不能隔开），同时数字之和最大的那一份的数字之和尽量小。

输入

输入的第一行包含两个正整数n，m。

接下来一行包含n个正整数。

输出

输出一个数，表示最优方案中，数字之和最大的那一份的数字之和。

样例1输入

5 2 （5个正整数，分成2份）2 1 2 2 3

样例1输出

5

样例1解释

若分成2和1、2、2、3，则最大的那一份是1+2+2+3=8；

若分成2、1和2、2、3，则最大的那一份是2+2+3=7；

若分成2、1、2和2、3，则最大的那一份是2+1+3或者是2+3，都是5；

若分成2、1、2、2和3，则最大的那一份是2+1+2+2=7。

所以最优方案是第三种，答案为5。

提示

[大家记得看到“最大的最小”这一类语言，一定要想二分能不能做。]

[我们二分最大的那一份的和d，然后从左向右分组，在一组中，在和不超过d的情况下尽量往右分。若最终分出来的组数小于等于m，则这显然是合法的（我们在分出来的组里随便找个地方切开，总能变到m组，且每组的和不超过d）]

[这个d显然是单调的，即，若和不超过d能分成m组，则和不超过d+1也是能分成m组的，故二分正确。]

问题分析将问题变成：要求最大的那一份数字之和不超过给定的一个数字d，问是否能划分成连续的m份。从左到右尽量将更多的元素划分进一个组里，这样可以得到"至少要分成多少份"，设为cnt，若cnt<=m，则能划分

暴力解法

从小到大枚举d来判断是否能划分成m份。

for(long long d=1; d<=r; ++d)

if(check(d,n,m,a))

return d;

二分查找

如果对于给定数字d能划分成m份，那对于d+1必然也能划分成m份。

一. 图解

二. 具体实现（C++版）（省略输入输出）

#include <bits/stdc++.h>

using namespace std;

// ================= 代码实现开始 =================

//判断a数组是否能分成不超过m份，满足每一份数字之和不超过d

//d:每一份数字之和不超过d

//n:a数组大小

//若能分成不超过m份，返回true；否则返回false

bool check(long long d, int n, int m, vector<int> &a){

long long sum = 0;//用于记录当前那一份的数字之和

int cnt = 1;//在每一份数字之和不超过d的情况下，至少要分成的份数

for(int i=0; i<n; ++i){

if(a[i]>d)//如果单个元素大于d，直接返回false

return false;

sum += a[i];

//如果加入了a[i]，超过了d

if(sum>d){

sum = a[i];

cnt = cnt+1;

}

}

return cnt <= m;

}

// 将所给数组分成连续的m份，使得数字之和最大的那一份的数字之和最小

// n：数组大小

// m：题中的m

// a：所给数组，大小为n

// 返回值：最优方案中，数字之和最大的那一份的数字之和

long long getAnswer(long long n, int m, vector<int> &a) {

//l表示答案下界，r表示答案上界

long long l = 1, r = 0;

//求出答案的初始上界r

for(int i=0; i<n; ++i){

r += a[i];

}

//暴力解法，从小到大枚举d来判断是否能分成m份

/* for(long long d=1; d<=r; ++d)

if(check(d,n,m,a))

return d;*/

//二分答案

while(l <= r){

long long mid = (l+r)>>1;//右移1位等于除以2

//[1,mid-1],mid,[mid+1,r]

if(check(mid,n,m,a))//验证mid可不可能为答案，如果可能,则答案在[1,mid]里，上界缩小

r = mid -1;

else//否则下界增大，答案在[mid+1,r]里

l = mid +1;

}

return r+1;//答案为r+1,因为r+1是最后一个满足check的mid值，否则mid就是答案时，执行了r=mid-1后，r最终还得+1回到mid

}

// ================= 代码实现结束 =================