二分答案巧思 | 四叶草の博客

一、二分答案介绍

二分查找是我们很熟悉的一种算法，通过对一个有序序列进行分割，最终能实现查找到目标数值。而二分答案就是基于这种思想衍生出来的解决最优化问题的策略。在题目中，我们最常看见的字眼就是最大值最小化或最小值最大化等目标，就在暗示我们使用二分答案算法。

从专业的角度来介绍二分答案算法，该算法基于二分的思想，通过对解空间进行不断分割，逐步逼近最优解。

今天这篇文章将结合具体例子，介绍笔者关于二分答案这个算法的应用范围的一点巧思

二、具体例子

以下这道题作为一个例子来介绍这个算法，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$ 。

输入格式

第 $1$ 行包含两个正整数 $N,M$ 。

第 $2$ 行包含 $N$ 个空格隔开的非负整数 $A_i$ ，含义如题目所述。

输出格式

一个正整数，即每段和最大值最小为多少。

输入输出样例 #1

输入 #1
1
2
5 3
4 2 4 5 1
输出 #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$ 。

观察这道题，要求每段和最大值最小，从直觉和做题经验上来说，就告诉我们，这道题应该用二分答案。

让我们回忆一下二分查找的基本结构

func binary_search(A, target)
  L = 0, R = A.length - 1
  while L<=R
     MID = (L + R) / 2
     if A[MID] < target
       L = MID + 1
     else if A[MID] > target
       R = MID -1
     else
       return MID
  return unsuccessful

类似于我们判断A[MID]与target的大小关系，我们需要判断当前我们二分分割出来的MID作为解，在给出的输入空间下，是否能实现。

如果能实现，我们是进入左区间/右区间，否则则进入右区间/左区间

那么在这道题的条件下，我们二分的结构即为：

cin >> n >> m;
for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    prefix[i] = prefix[i - 1] + a[i];
}
ll l = 1, r = prefix[n], mid = 0;
while (l <= r) {
    mid = (l + r) / 2;
    if (check(mid))
        r = mid - 1;
    else
        l = mid + 1;
}
cout << r + 1 << "\n";

在这道题中，check()的功能即为判断，是否存在一种符合条件的方案能实现mid作为每段和的最大值

容易想到（笔者也不知道怎么想到的，也不会证明，反正做题经验如此（笑）），

我们遍历整个序列，不断累加当前段的和，如果大于当前mid的值，便重新开启一个新的子段进行累加，最终判断子段的数量是否小于等于我们的规定的最大子段数量

bool check(ll maxn) {
    ll res = 1, cur_sum = 0;
    for (int i = 1; i <= n; ++i) {
        if (a[i] > maxn) return false;
        if (cur_sum + a[i] > maxn) {
            cur_sum = 0;
            res += 1;
        }
        cur_sum += a[i];
    }
    return res <= m;
}

所以最终的题解如下：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 10;
ll n, m, prefix[N], a[N];
bool check(ll maxn) {
    ll res = 1, cur_sum = 0;
    for (int i = 1; i <= n; ++i) {
        if (a[i] > maxn) return false;
        if (cur_sum + a[i] > maxn) {
            cur_sum = 0;
            res += 1;
        }
        cur_sum += a[i];
    }
    return res <= m;
}
int main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        prefix[i] = prefix[i - 1] + a[i];
    }
    ll l = 1, r = prefix[n], mid = 0;
    while (l <= r) {
        mid = (l + r) / 2;
        if (check(mid))
            r = mid - 1;
        else
            l = mid + 1;
    }
    cout << r + 1 << "\n";
    return 0;
}