数列分段 Section II
题目描述
对于给定的一个长度为N的正整数数列 \(A_{1\sim N}\)，现要将其分成 \(M\)（\(M\leq N\)）段，并要求每段连续，且每段和的最大值最小。
关于最大值最小：
例如一数列 \(4\ 2\ 4\ 5\ 1\) 要分成 \(3\) 段。
将其如下分段：
第一段和为 \(6\)，第 \(2\) 段和为 \(9\)，第 \(3\) 段和为 \(1\)，和最大值为 \(9\)。
将其如下分段：
第一段和为 \(4\)，第 \(2\) 段和为 \(6\)，第 \(3\) 段和为 \(6\)，和最大值为 \(6\)。
并且无论如何分段，最大值不会小于 \(6\)。
所以可以得到要将数列 \(4\ 2\ 4\ 5\ 1\) 要分成 \(3\) 段，每段和的最大值最小为 \(6\)。
输入格式
第 \(1\) 行包含两个正整数 \(N,M\)。
第 \(2\) 行包含 \(N\) 个空格隔开的非负整数 \(A_i\)，含义如题目所述。
输出格式
一个正整数，即每段和最大值最小为多少。
样例 #1
样例输入 #1
5 3
4 2 4 5 1
样例输出 #1
6
提示
对于 \(20\%\) 的数据，\(N\leq 10\)。
对于 \(40\%\) 的数据，\(N\leq 1000\)。
对于 \(100\%\) 的数据，\(1\leq N\leq 10^5\)，\(M\leq N\)，\(A_i < 10^8\)， 答案不超过 \(10^9\)。
解析&代码
二分答案
先介绍下二分答案吧
比如我们要从一本英汉词典上查一个单词，如果你从头到尾一页一页的翻着找（并仔细一点），这样找可以保证一定能找到，但是最坏情况你要把整本词典都翻一遍，那就麻烦了（而且很累）。
有什么改进的方法吗？当然有。
我们考虑把这个词典从中间分开，看一下中间那一页的主要单词都是啥，然后去判断我要找的单词应该在左半部分还是右半部分，再去那一部分考虑怎么找就好了。同样的，在另一部分也是要进行划分并且判断的操作。这样一直进行下去，便能很快的找到答案，而且根本不需要翻过整个词典来。
可以证明，如果一页一页的找，最多要找 \(n\) 次，但是用这个方法，最多找\(floor(log2n)\)次。
我们把这个方法叫做“二分答案”。顾名思义，它用二分的方法枚举答案，并且枚举时判断这个答案是否可行。但是，二分并不是在所有情况下都是可用的，使用二分需要满足两个条件:
-
有上下界
-
区间有单调性
二分答案应该是在一个单调闭区间上进行的。也就是说，二分答案最后得到的答案应该是一个确定值，而不是像搜索那样会出现多解。二分一般用来解决最优解问题。刚才我们说单调性，那么这个单调性应该体现在哪里呢？
可以这样想，在一个区间上，有很多数，这些数可能是我们这些问题的解，换句话说，这里有很多不合法的解，也有很多合法的解。我们只考虑合法解，并称之为可行解。考虑所有可行解，我们肯定是要从这些可行解中找到一个最好的作为我们的答案， 这个答案我们称之为最优解。
最优解一定可行，但可行解不一定最优。我们假设整个序列具有单调性，且一个数x为可行解，那么一般的，所有的 \(x'(x'<x)\) 都是可行解。并且，如果有一个数y是非法解，那么一般的，所有的 \(y'(y'>y)\) 都是非法解。
那么什么时候适用二分答案呢？注意到题面：使得选手们在比赛过程中的最短跳跃距离尽可能长。如果题目规定了有“最大值最小”或者“最小值最大”的东西，那么这个东西应该就满足二分答案的有界性（显然）和单调性（能看出来）。
所以（快点）上代码吧。。。
#include <bits/stdc++.h>
using namespace std;
int n,m,a[100010],l,r;
int f(int x)
{
int ret=0,last=0;
for(int i=1;i<=n;i++)
{
if(last+a[i]<=x)
{
last+=a[i];
}
else{
ret++;
last=a[i];
}
}
return ret;
}
int main()
{
cin >> n >> m;
for(int i=1;i<=n;i++)
{
cin >> a[i];
}
for(int i=1;i<=n;i++)
{
l=max(l,a[i]);
r+=a[i];
}
while(l<r)
{
int mid=(l+r)/2;
if(f(mid)>=m)
{
l=mid+1;
}
else{
r=mid;
}
}
cout << l;
return 0;
}