P1182 数列分段 Section II

发表于 更新于

P1182 数列分段 Section II

题目描述

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

关于最大值最小：

例如一数列 $4\ 2\ 4\ 5\ 1$ 要分成 $3$ 段。

将其如下分段：

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

将其如下分段：

第一段和为 $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$。

思路分析 + 代码实现

题目求的是“最大的最小”，所以采用二分答案的方法。对于每个 $mid$ ，检查是否能将数组分成不超过 $M$ 段，使得每段和不超过 $mid$。如果可以，说明 $mid$ 是一个可行解，尝试更小的 $mid$ ；如果不行，说明 $mid$ 太小，需要增大 $mid$ 。

二分查找的核心是判断是否能将数组分成 $cnt <= M$ 段，使得每段的和都不超过 $mid$ 。我们用变量 $acc$ 累计本段的和，当 $acc + a[i] > mid$ 时，分出一段，让 $a[i]$ 在新一段的开头，并更新 $cnt$ 和 $acc$ 。但是！有一个细节要注意，这个逻辑能正确工作，有一个隐含的前提： $mid$ 必须大于等于数组中的最大元素 $ma$ 。如果 $mid < ma$，那么数组中存在至少一个元素 $a[i] = ma$，它无法被任何一段容纳（因为 $a[i] > mid$），在这种情况下，判断的逻辑就失效了。所以在读入的过程中记录 $ma$ ，二分时将 $l$ 设为 $ma$ 即可解决。代码如下，时间复杂度 $O(n\operatorname{log}n)$ 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
using namespace std;
constexpr int MAXN = 1e5 + 5;
int a[MAXN];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, M, ma = 0;
    cin >> N >> M;
    for(int i = 0; i < N; i++) {
        cin >> a[i];
        ma = max(ma, a[i]);
    }
    int l = ma, r = 1e9, ans;
    while (l <= r) {
        int mid = (l + r) / 2, cnt = 1, acc = 0;
        for(int i = 0; i < N; i++) {
            int t = a[i] + acc;
            if (t > mid) {
                cnt++;
                acc = a[i];
            } else acc = t;
        }
        if (cnt <= M) {
            ans = mid;
            r = mid - 1;
        } else l = mid + 1;
    }
    cout << ans;
    return 0;
}