Balancing Bacteria

题意

有 $N$ 块草地，第 $i$ 块草地当前与健康值的差为 $a_i$ 。目标是把所有 $a_i$ 都变成 $0$ 。

一次操作选择一个功率 $L$ ，会影响最右边连续 $L$ 块草地。

如果使用“增加细菌”的药，则这 $L$ 块草地从左到右分别增加：

text

11, 2, 3, ..., L

如果使用“去除细菌”的药，则分别减少这些值。

求最少操作次数。

思路

先看一个从左到右直接修正的小数据模拟：

cpp

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 16:11
 * update_at: 2026-07-11 16:12
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1005;

int n;
long long a[MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    long long ans = 0;

    // 小数据朴素模拟：从左到右把当前位置修成 0，并直接更新后缀。
    for (int i = 1; i <= n; i++) {
        long long op = -a[i];
        ans += llabs(op);

        for (int j = i; j <= n; j++) {
            a[j] += op * (j - i + 1);
        }
    }

    cout << ans << '\n';

    return 0;
}

暴力的想法是：处理到第 i 块草地时，之后的操作再也不会影响 i 左边的位置。因此可以立刻决定从 i 开始的后缀操作次数，把 a[i] 修成 0。这种写法每次会更新后缀，复杂度是 $O(N^2)$ 。

满分做法用二阶差分把操作变简单。

定义一阶差分：

b_i = a_i - a_{i-1}

其中 $a_0=0$ 。

再定义二阶差分：

c_i = b_i - b_{i-1}

其中 $b_0=0$ 。

假设一次“增加细菌”的操作从位置 $h$ 开始影响后缀，那么它给原数组增加：

text

1
20, 0, ..., 0, 1, 2, 3, ...
              h

观察差分变化：

在原数组中，从 $h$ 开始是斜率为 $1$ 的递增序列。
到一阶差分里，它会让从 $h$ 开始的后缀都增加 $1$ 。
到二阶差分里，只剩下第 $h$ 个位置增加 $1$ 。

“去除细菌”的操作同理，只会让二阶差分的某一个位置减少 $1$ 。

所以每次操作本质上就是：

text

1把二阶差分数组 c 的某一个位置 +1 或 -1

要把原数组全部变成 $0$ ，等价于把二阶差分也全部变成 $0$ 。每个位置互不影响，因此最少操作次数就是：

\sum_{i=1}^{N} |c_i|

样例一 a = [-1, 3]：

i	$a_i$	$b_i=a_i-a_{i-1}$	$c_i=b_i-b_{i-1}$
1	-1	-1	-1
2	3	4	5

答案为：

|-1| + |5| = 6

代码

cpp

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 16:11
 * update_at: 2026-07-11 16:12
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200005;

int n;
long long a[MAXN];
long long diff1[MAXN];
long long diff2[MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    for (int i = 1; i <= n; i++) {
        diff1[i] = a[i] - a[i - 1];
    }
    for (int i = 1; i <= n; i++) {
        diff2[i] = diff1[i] - diff1[i - 1];
    }

    long long ans = 0;
    for (int i = 1; i <= n; i++) {
        ans += llabs(diff2[i]);
    }

    cout << ans << '\n';

    return 0;
}

复杂度

只需要线性计算两次差分。

时间复杂度为 $O(N)$ ，空间复杂度为 $O(N)$ 。

总结

本题的关键是把“后缀上加一个等差数列”看成差分变化。

一阶差分后，它变成“后缀统一加一”；二阶差分后，它只影响一个点。这样每个位置都独立，答案就是二阶差分绝对值和。

目录

题意

思路

代码

复杂度

总结