把数列变成 0 的最少操作

一句话算法

把正数和负数看成两堆高度，能配对就一起消，最后答案是两堆总高度的较大值。

问题模型

给定一个整数序列。一次操作可以让一个正数减 1，或者让一个负数加 1；如果同时存在正数和负数，也可以理解为一次操作同时消掉两边各 1 的量。

目标是让所有数变成 0，求最少操作次数。

核心直觉

所有正数一共需要被减掉：

所有负数一共需要被加回来：

一次操作最多同时消掉正数堆和负数堆各一层，所以能配对的部分是 min(P,N)。剩下没法配对的部分还要单独消掉。

因此答案是：

算法步骤

1. 初始化 positive_sum = 0，negative_abs_sum = 0。
2. 扫描每个数：
   • 如果 x > 0，累加到 positive_sum。
   • 如果 x < 0，把 -x 累加到 negative_abs_sum。
3. 输出 max(positive_sum, negative_abs_sum)。

算法证明

下界： 正数总量至少要被消掉 P 次，负数总量至少要被消掉 N 次。一次操作最多让两边各减少 1，所以操作次数至少是 max(P,N)。

构造： 每次如果两边都还有量，就同时消掉一层；如果某一边已经没了，就只消另一边。这样总共正好需要 max(P,N) 次。

下界能达到，所以答案就是 max(P,N)。

复杂度分析

• 时间复杂度：$O(n)$。
• 空间复杂度：$O(1)$。

代码实现

        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

        #include <bits/stdc++.h>
using namespace std;

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

    int n;
    cin >> n;

    long long positive_sum = 0;
    long long negative_abs_sum = 0;

    for (int i = 0; i < n; ++i) {
        long long x;
        cin >> x;
        if (x > 0) positive_sum += x;
        else negative_abs_sum += -x;
    }

    cout << max(positive_sum, negative_abs_sum) << '\n';
    return 0;
}
    

测试用例

输入：

5
10 -8 -5 2 1

输出：

13

正数总量为 13，负数绝对值总量为 13，可以完全配对消掉。

应用分类详解

这个模型的本质是“正负两类资源可以配对抵消，答案由更大的总需求决定”。

一、正负抵消模型

典型模式： 一类操作减少正数，一类操作增加负数，正负可以配对。 识别信号： 题面出现“同时选择一个正数和一个负数操作”。 核心建模： 分别统计两边总需求，答案取较大值。

二、供需平衡模型

典型模式： 一边是供给，一边是需求，单位操作可以匹配一个供给和一个需求。 识别信号： 题面可以抽象成两堆量互相抵消。 核心建模： 先配对公共部分，再处理剩余部分。

经典例题

1. luogu-P1031 均分纸牌。虽然有相邻限制，但核心仍是多余量和缺少量的平衡。

2. 本文模型 适合练习把“每次操作改变一到两个数”转成正负两堆总量的下界与构造。