Problem
考察知识点：二分、贪心。
题目描述
对于给定的一个数组，现要将其分成 \(M\) 段，并要求每段连续，且每段和的最大值最小。
思路
二分答案出每段和最大值的最小值，然后贪心检验是否满足。
难点在 \(check\) 上。
策略：每次开始循环，如果没有超范围，就一直选，知道选满为止，求最大值。
代码
#include <iostream>
using namespace std;
int n,m,a[100005],l,r,mid,ans;
//二分的是：区间和的最大值。
//左右边界：最多分成n段，最大值为本身。最少就1段，最大值就是和。
bool check(int mid) {
int sum = 0,cnt = 0;;
for (int i = 1;i <= n;i++) {
if (sum + a[i] <= mid) sum += a[i];
else sum = a[i],cnt++;//段数+1
}
return cnt >= m; //是否存在数量>=m的区间
}
int main() {
scanf("%d%d",&n,&m);
for(int i = 1;i <= n;i++)
scanf("%d",&a[i]),l = max(l,a[i]),r += a[i];
while (l <= r) {
mid = (l + r) >> 1;
if (check(mid)) l = mid + 1;
else r = mid - 1;
}
printf("%d",l);
return 0;
}