# 导引

用一个简单的题目 P1182 数列分段 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$。
要求输出每段和最大值最小为多少。

不妨假设每段的长度为 $i_1, i_2, \dots, i_M$，于是，我们可以如下描述所求答案： $$ ans = \mathop{\arg\min}(\max(\sum^{i_1}{i=1}A_i, \sum^{i_2}{i=i_1+1}A_i, \dots, \sum^{i_M}{i=i{M-1}+1}A_i)) $$ 可以发现，$ans$ 的取值范围是一个确定的区间： $$ \max(A_{1\sim N}) \leq ans \leq \sum^N_{i=1}A_i $$ 既然有着一个确定的区间，那么一个朴素的想法就是从最小向最大枚举这个区间内的所有值（因为是整数，所以是可数的），直到找到一个合法值。

但如何判断这个值是否合法？

由于段数是给定的，那么，我们只需要对段数的合法性进行判断即可：

计算前 $i$ 项和，若小于等于当前枚举的值，那么继续累加
若大于当前枚举的值，意味着枚举值并不是这一段的和，于是在此设置分段点，将前缀和清零。

代码如下：

bool judge(vector<int>& a, int m, int val){
    int sum = 0, cnt = 0;
    for(auto& a_i: a){
        if(sum + a_i <= val)
            sum += a_i;
        else
            sum = a_i, cnt++;
    }
    return cnt > m; // 代表划分的段多于规定，可以推断出 val 偏小
}

显然，这样我们的算法复杂度是 $O(N \times \sum^N_{i=1}A_i)$ 。

这样的复杂度，在序列之和较大时是无法接受的，于是我们有一种更好的方法。

# 二分枚举

既然是在一段区间内枚举，显然我们可以使用二分的方式来枚举答案。

事实上，这和二分搜索有着相似的地方，同样是一个递增/递减的序列，同样有着判断条件，只是二分枚举时的判断条件不是一个简单的等于号。

此题的代码如下：

int binary_answer(vector<int>& a, int m){
    int l = -10000, r = 0;
    for(auto& a_i: a){
        l = max(l, a_i);
        r += a_i;
    }
    while(l <= r){
        int mid = (l + r) >> 1;
        if(judge(a, m, mid))
            l = mid + 1;
        else 
            r = mid - 1;
    }
    return l;
}

这样，算法的时间复杂度就可以降低为 $O(N \times \log{\sum^N_{i=1}A_i})$ （乍一看好像没什么提升）

# 总结

二分答案可以概括为：在答案合法的条件下不断逼近最优，最后一个合法的答案就是最优解。

这种方法事实上可以解决普通枚举无法解决的事情：在实数域内枚举值。我们无法通过常规的枚举来枚举实数域内的值，但是通过二分的方式，我们确实能够做到在一个区间内找到这个实数。

这里提供一套板子

整数域

while(l <= r){
    mid = (l + r) >> 1;
    if(judge(mid))
        ans = mid, l = mid + 1;
    else 
        r = mid - 1;
}

实数域

while(abs(r - l) > eps){
    mid = (l + r) / 2;
    if(judge(mid))
        l = mid;
    else 
        r = mid;
}
//eps根据题目要求的精度来取，一般比精度多取3位即可

# 题外话

Problem - 1216E2 - Codeforces 一个稍难一些的二分答案

Binary Answer

二分答案（不是二分搜索）（蓝旭算法课）

# 导引

# 二分枚举

# 总结

# 题外话