「洛谷 P1182」数列分段 Section II - 二分答案

发表于 更新于 分类于 ， 阅读次数： Disqus：

学完 wxk 的康复训练

学 wxk 学久了感觉 wxk 有意思，学 OI 学久了感觉 OI 有意思。 ——huaruoji

题意描述

洛谷链接

给定一个长度为 \(n\) 的整形数列 \(A_{1 \sim n}\)，先将其分为 \(m\) 段，并要求每段连续，目前需要一种分法，使得分出的每段和的最大值最小。

解题思路

整体框架

求最大值最小，显然是一道二分答案题，可以尝试使用二分答案解决问题。

这道题二分答案的方法是二分每段和的最大值，从答案的最大值 \(10^9\) 开始二分。注意二分的最小值为整个数列的单个元素最大值，否则可能会出现最后答案小于数列中的某个数，导致无法分割数列的情况（例如洛谷数据中的第四个测试点）。

1
2
3
4
5
6
7
8
9
10
11
12
int l = 1, r = MAXN * MAXA;
for (int i = 0; i < n; i++) {
    std::cin >> a[i];
    if (a[i] > l) l = a[i];
}

while (l < r) {
    int mid = (l + r) >> 1;
    // 二分处理
}

std::cout << l << std::endl;

细节处理

现在我们已经处理完了，现在的问题是二分出答案后如何检验。

这块可以使用类似均分纸牌的思路，使用贪心解决。

在数列的开头开始扫，不停的加数列中的数，若和大于答案，则把和清空为最后加入的一个数，段数 +1。

1
2
3
4
5
6
7
8
int cnt = 1, sum = 0;
for (int i = 0; i < n; i++) {
    sum += a[i];
    if (sum > mid) {
        sum = a[i];
        cnt++;
    }
}

最后如果段数大于 \(m\)，则说明答案过小，答案在 \(mid\) 之上。

如果段数小于 \(m\)，则说明答案过大，答案在 \(mid\) 之下。

1
2
if (cnt <= m) r = mid;
if (cnt > m) l = mid + 1;

代码演示

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
32
33
34
35
36
#include <iostream>

const int MAXN = 100000, MAXA = 10000;

int main() {
    int n, m;
    static long long a[MAXN];

    std::cin >> n >> m;

    int l = 1, r = MAXN * MAXA;
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
        if (a[i] > l) l = a[i];
    }

    while (l < r) {
        int mid = (l + r) >> 1;

        int cnt = 1, sum = 0;
        for (int i = 0; i < n; i++) {
            sum += a[i];
            if (sum > mid) {
                sum = a[i];
                cnt++;
            }
        }

        if (cnt <= m) r = mid;
        if (cnt > m) l = mid + 1;
    }

    std::cout << l << std::endl;

    return 0;
}