洛谷 P1182 数列分段 Section II 二分详细讲解
根据题意可以看出，我们二分的，每段和的最大值的，左边界为数组中最大的一个数，右边界为所有数之和。
我们可以二分这个每段和的最大值，找出满足m段的最小值
根据图来理解代码的注解
const int N = 1e5 + 10;
int n,m;
int a[N];
bool check(int x)
{
int cnt = 0,sum = 0;//段数，每段的总和
for (int i = 1;i <= n;i ++)
{
if (sum + a[i] <= x) sum += a[i];
else cnt ++,sum = a[i];
}
cnt ++;//记录最后一段
return cnt > m;//段数>m,说明当前这个最大值偏小
}
void solve()
{
cin >> n >> m;
int maxn = 0,sum = 0;
for (int i = 1;i <= n;i ++)
cin >> a[i],maxn = max(maxn,a[i]),sum += a[i];
int l = maxn - 1,r = sum + 1;//根据题意可以看出，左边界为maxn，右边界为sum。这样写是为了将取值范围扩大，避免边界出错
while(l + 1 != r)
{
int mid = l + r >> 1;//二分最大值
if (check(mid)) l = mid;//mid偏小
else r = mid;
}
cout << r << endl;//输出边界线的右边
}