导引#

用一个简单的题目 P1182 数列分段 Section II 来讨论这个算法

题目描述

不妨假设每段的长度为，于是，我们可以如下描述所求答案：

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

既然有着一个确定的区间，那么一个朴素的想法就是从最小向最大枚举这个区间内的所有值（因为是整数，所以是可数的），直到找到一个合法值。

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

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

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

代码如下：

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 偏小
}

显然，这样我们的算法复杂度是。

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

二分枚举#

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

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

此题的代码如下：

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;
}

这样，算法的时间复杂度就可以降低为（乍一看好像没什么提升）

总结#

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

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

这里提供一套板子

整数域

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 一个稍难一些的二分答案