数列分段 Section II
题目描述
对于给定的一个长度为N的正整数数列 \(A_{1\sim N}\)，现要将其分成 \(M\)（\(M\leq N\)）段，并要求每段连续，且每段和的最大值最小。
关于最大值最小：
例如一数列 \(4\ 2\ 4\ 5\ 1\) 要分成 \(3\) 段。
将其如下分段：
\[[4\ 2][4\ 5][1] \]第一段和为 \(6\)，第 \(2\) 段和为 \(9\)，第 \(3\) 段和为 \(1\)，和最大值为 \(9\)。
将其如下分段：
\[[4][2\ 4][5\ 1] \]第一段和为 \(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;
}