二分答案

导引

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

题目描述

Example

对于给定的一个长度为 N 的正整数数列 $A_{1\sim N}$，现要将其分成 $M$（$M\le N$）段，并要求每段连续，且每段和的最大值最小。

关于最大值最小：

例如一数列 $42451$ 要分成 $3$ 段。

将其如下分段：

$[42][45][1]$

第一段和为 $6$，第 $2$ 段和为 $9$，第 $3$ 段和为 $1$，和最大值为 $9$。

将其如下分段：

$[4][24][51]$

第一段和为 $4$，第 $2$ 段和为 $6$，第 $3$ 段和为 $6$，和最大值为 $6$。

并且无论如何分段，最大值不会小于 $6$。

所以可以得到要将数列 $42451$ 要分成 $3$ 段，每段和的最大值最小为 $6$。

要求输出每段和最大值最小为多少。

不妨假设每段的长度为 $i_1,i_2,\dots ,i_M$， 于是，我们可以如下描述所求答案：

$$ans=\mathrm{argmin}(\max (\sum _{i=1}^{i_1}{A}_i,\sum _{i=i_1+1}^{i_2}{A}_i,\dots ,\sum _{i=i_{M-1}+1}^{i_M}{A}_i))$$

可以发现，ans 的取值范围是一个确定的区间：

$$\max (A_{1\sim N})\le ans\le \sum _{i=1}^N{A}_i$$

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

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

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

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

代码如下：

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

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

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

二分枚举

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

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

此题的代码如下：

1
int binary_answer(vector<int>& a, int m){
2
    int l = -10000, r = 0;
3
    for(auto& a_i: a){
4
        l = max(l, a_i);
5
        r += a_i;
6
    }
7
    while(l <= r){
8
        int mid = (l + r) >> 1;
9
        if(judge(a, m, mid))
10
            l = mid + 1;
11
        else
12
            r = mid - 1;
13
    }
14
    return l;
15
}

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

总结

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

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

这里提供一套板子

• 整数域

1
while(l <= r){
2
    mid = (l + r) >> 1;
3
    if(judge(mid))
4
        ans = mid, l = mid + 1;
5
    else
6
        r = mid - 1;
7
}

• 实数域

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

题外话

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