「ZJOI2020」序列 - 贪心

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

题意描述

洛谷链接

LibreOJ 链接

Bob 喜欢序列。

有一个长度为 \(n\) 的非负整数序列 \(a_1, a_2,\cdots, a_n\)。每一步你可以从以下三种操作中选择一种执行：

  • 选择一个区间 \([l, r]\)，将下标在这个区间里的所有数都减 \(1\)。
  • 选择一个区间 \([l, r]\)，将下标在这个区间里且下标为奇数的所有数都减 \(1\)。
  • 选择一个区间 \([l, r]\)，将下标在这个区间里且下标为偶数的所有数都减 \(1\)。

求最少需要多少步才能将序列中的所有数都变成 \(0\)。

对于所有的数据，\(1 \leq n \leq 100000, 0 \leq a_i \leq 10^9, 1 \leq T \leq 10\)。

解题思路

我甚至菜到这是我做得第一道黑题

模型构建

对于这道题，我们可以用基于贪心的思想解决。

首先明确两个概念：

  1. 对于第一种情况，由于在区间中减去的数是连续的，我们可以将其形象地称为 直线，命名为变量 \(\text{line}_i\)；
  2. 对于第二种情况，由于在区间中减去的数是不连续且有规律的间隔的，我们可以将其形象地称为 跳线，命名为变量 \(\text{dance}_i\)。

基于类似于数学归纳法的思想，我们可以设想对于第 \(i\) 个数，前面的 \(i - 1\) 个数中每个数 \(a_j\) 在使用了 \(\text{line}_j\) 个直线和 \(\text{dance}_j\) 个跳线的情况下全部处理为 \(0\)。在这种情况下求需要总共 \(\text{line}_i\) 个直线与 \(\text{dance}_i\) 个跳线将前 \(a_i\) 个数全部处理为 \(0\)，同时统计总共使用的线的数量 \(\text{ans}\)。

对于初始化，显然 \(\text{line}_0 = \text{dance}_0 = \text{ans} = 0\)。

情况分析

接下来我们需要分析对于 \(a_i\)，我们使用直线或跳线的情况。

显然这只有下列两种情况：

  1. 在相邻两项 \(\forall i\)，\(a_i > 0\)。我们可以形象地称这个范围是连续的，显然在此时直线和跳线均可使用。在此时 尽量使用直线 必定是最优答案的一种。
  2. 在相邻两项 \(\exists i\)，\(a_i = 0\)。我们可以形象地称这个范围是不连续（跳跃）的，显然此时只能使用跳线。

对于情况 \(1\)，以下为证明：

我们可以将该区间分为两部分：\(a_i = b_i + c\)，只用跳线处理 \(b_i\)。其中 \(c \leq \min\limits_{l \leq i \leq r}\{a_i\}\)。显然对于 \(c\) 直接使用直线搞定是最优的。而对于 \(b_i\) 为连续区间的前提下使用直线处理所作用的区间是用跳线的两倍。故要使 \(b_i\) 仅用跳线处理下最优，我们需要让 \(b_i\) 直线可作用区间 极小，即不可用直线。此时 \(b_i\) 必定不连续，显然此时 \(c = \min\limits_{l \leq i \leq r}\{a_i\}\)。故用 尽量多的直线 处理掉 \(c\)，剩下的 不连续 的 \(b\) 用跳线处理。这种操作定是最优答案的一种。

分类讨论

接下来我们就可以进行分类讨论。我们的目标是将 \(a_i\) 处理为 \(0\)，故遍历到 \(i\) 时，增加的线的数量必定为 \(a_i\)。答案的增量显然是增加线的数量，即 \(\text{ans} = \text{ans} + a_i\)。显然我们只考虑 \(a_i\) 无法取到最优，于是我们可以从 \(a_{i + 1}\) 入手。

  1. \(\text{line}_{i - 1} + \text{dance}_{i - 1} \leq a_{i + 1}\)：此时已用的线不够为 \(a_{i + 1}\) 作准备，我们需要更多的线来做准备。我们可以先将之前的两种线对 \(a_{i + 1}\) 的作用效果反映出来，即 \(a_{i + 1} = a_{i + 1} - \text{line}_{i - 1} - \text{dance}_{i - 1}\)，此时 \(a_{i + 1} > 0\)。 此时只考虑 \(a_{i + 1}\) 是无法做出最优解法的，我们必须同时考虑 \(a_i\)：

    1. $a_i \leq a_{i + 1}$：显然全部使用直线即可将 $a_i$ 处理为 $0$。即 $\text{line}_i = \text{line}_{i - 1} + a_i$，$\text{dance}_i = \text{dance}_{i - 2}$，$a_{i + 1} = a_{i + 1} - a_i$，$a_i = 0$；

2. $a_i > a_{i + 1}$：先使用 $a_{i + 1}$ 条直线覆盖，再使用 $a_{i + 1} - a_i$ 条相邻的跳线覆盖，可将 $a_i$ 处理为 $0$。即 $\text{line}_i = \text{line}_{i - 1} + a_{i + 1}$，$\text{dance}_{i + 1} = \text{dance}_{i - 1} + a_i - a_{i + 1}$，$a_i = a_{i + 1} = 0$。

  2. \(\text{line}_{i - 1} + \text{dance}_{i - 1} > a_{i + 1}\)：说明目前我们拥有的线为 \(a_{i + 1}\) 准备过剩了。此时我们就需要考虑停止一些线的作用范围。我们可以记录需要额外停止的数量 \(\Delta = \text{line}_{i - 1} + \text{dance}_{i - 1} - a_{i + 1}\)。由于我们可以发现两种线均与位置有关，故在处理好 \(\Delta\) 后我们需要 \(\text{line}_{i - 1} = \text{line}_{i - 1} - \Delta\)，\(\text{dance}_{i - 1} = \text{dance}_{i - 1} - \Delta\)。同时记录 \(\text{nxt} = \Delta\)，表示有 \(\Delta\) 条线可从 \(a_{i + 1}\) 恢复出发。这样就可以把该情况转化为情况 \(1\)。处理恢复情况则可在情况 \(1\) 处理后再把 \(\text{nxt}\) 加回去，同时在答案中减去可恢复的线的数量。即 \(a_{i + 1} = a_{i + 1} + \text{nxt}\)，\(\text{ans} = \text{ans} - \text{nxt}\)。但由于在处理 \(\Delta\) 时 \(\text{line}_{i - 1}\) 和 \(\text{dance}_{i - 1}\) 不能处理为负数，故有下列几种情况特殊考虑：

    1. \(\Delta > \text{dance}_{i - 1}\)：这是我们需要直接停止部分的直线，让直线刚好覆盖 \(a_{i + 1}\)。即 \(\text{line}_{i - 1} = a_{i + 1}\)，此时 \(\Delta\) 随之变化，即 \(\Delta = \text{dance}_{i - 1}\)

    2. \(\Delta > \text{line}_{i - 1}\)：这时我们需要直接停止部分的跳线，让跳线刚好覆盖 \(a_{i + 1}\)。即 \(\text{dance}_{i - 1} = a_{i + 1}\)，此时 \(\Delta\) 随之变化，即 \(\Delta = \text{line}_{i - 1}\)

    3. 情况 \(1\)、\(2\) 均不符合，保持现状。

最后我们需要解决奇数项和偶数项不同跳线的问题。由于两种跳线可看作作用相同的线，我们可以用两个变量存储两种跳线，然后在遍历 \(a_i\) 的跳线不同作用项时不停交换即可，即每遍历到下一项则两种跳线数据交换。

最终时间复杂度为 \(O(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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <cstdio>
#include <algorithm>

const int MAXN = 100000;

int main() {
    int t;

    scanf("%d", &t);

    while (t--) {
        int n;
        static long long a[MAXN + 2];

        scanf("%d", &n);

        for (int i = 1; i <= n; i++) {
            scanf("%lld", &a[i]);
        }

        long long line = 0, dance1 = 0, dance2 = 0, ans = 0, nxt = 0;

        for (int i = 1; i <= n; i++) {
            if (a[i + 1] < dance1 + line) {
                int delta = dance1 + line - a[i + 1];

                if (delta > dance1) {
                    line = a[i + 1];
                    delta = dance1;
                }

                if (delta > line) {
                    dance1 = a[i + 1];
                    delta = line;
                }

                line -= delta;
                dance1 -= delta;
                nxt = delta;
                a[i + 1] -= nxt;
            }

            a[i + 1] -= line + dance1;
            ans += a[i];

            if (a[i] <= a[i + 1]) {
                line += a[i];
                a[i + 1] -= a[i];
                a[i] = 0;
            } else {
                line += a[i + 1];
                dance2 += a[i] - a[i + 1];
                a[i] = a[i + 1] = 0;
            }

            a[i + 1] += nxt;
            ans -= nxt;
            nxt = 0;

            std::swap(dance1, dance2);
        }

        printf("%lld\n", ans);
    }

    return 0;
}