数组清零 题解

题目分析

本题要求我们模拟一个特定的过程，并计算将数组中所有元素变为零所需的总操作次数。
数组由非负整数组成，每次操作严格按照以下规则执行：

1. 找到当前最大元素，若有多个则选择下标最大的那个，记下标为 $k$。
2. 在所有不为零的元素中找到最小值，记为 $a_j$。
3. 将选出的 $a_k$ 减去 $a_j$（$a_k \gets a_k - a_j$）。

重复这一过程，直到数组全为零。题目保证在有限步内结束，我们只需要输出操作次数。

数据范围很小：$n \le 100$，$a_i \le 100$。因此可以直接模拟每一步操作。

解题思路

由于 $n$ 和 $a_i$ 的上限仅为 $100$，即使在最坏情况下，操作次数也不会太大。我们来估算一下上界：

• 每次操作至少会将某个元素的值减少 $1$（因为最小值 $a_j \ge 1$）。
• 数组中所有元素的初始值之和 $\sum a_i \le 100 \times 100 = 10000$。
• 每次操作减少的总和等于 $a_j \ge 1$，因此总操作次数不可能超过初始总和 $10000$。

每次操作需要扫描一遍数组寻找最大值和最小值，扫描复杂度为 $O(n)$。因此总时间复杂度约为 $O(\text{操作次数} \times n) \le 10^4 \times 100 = 10^6$，完全可以在 $1000\text{ms}$ 内轻松运行完成。

因此我们直接按照题目描述编写模拟过程即可。

算法说明

1. 读入 $n$ 和数组 $a$，下标从 $1$ 开始方便理解。
2. 用一个变量 cnt 记录操作次数，初始为 $0$。
3. 不断执行以下循环，直到所有元素都变成 $0$：
   • 寻找最大值中下标最大的元素：遍历数组，对于每个 $i$，若 a[i] >= a[mx] 则更新 mx = i（等号保证下标最大）。
   • 若找到的最大值 a[mx] == 0，说明数组中所有元素都是 $0$，循环结束。
   • 寻找所有非零元素中的最小值：先令 mn = a[mx]，然后遍历数组，若 a[i] > 0 则 mn = min(mn, a[i])。
   • 进行减法操作：a[mx] -= mn。
   • 操作次数加一：cnt++。
4. 循环结束后，输出 cnt。

参考代码

下面是 C++ 实现，与题目提供的参考代码一致，并逐段添加了注释。

cpp
复制
1#include <cstdio>
2#include <algorithm>
3using namespace std;
4
5const int N = 105;
6int n;
7int a[N];
8int cnt;
9
10int main() {
11    // 读入数据
12    scanf("%d", &n);
13    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
14    
15    // 模拟操作
16    while (1) {
17        // 1. 找到最大元素中下标最大的
18        int mx = n;  // 初始假设最后一个最大
19        for (int i = 1; i <= n; i++)
20            if (a[i] >= a[mx]) mx = i;
21        
22        // 如果最大值已经是 0，说明数组全为零，退出
23        if (a[mx] == 0) break;
24        
25        // 2. 找到所有非零元素中的最小值
26        int mn = a[mx];  // 初始值设为最大值（保证会被更小的非零值更新）
27        for (int i = 1; i <= n; i++)
28            if (a[i] > 0) mn = min(mn, a[i]);
29        
30        // 3. 执行减法
31        a[mx] -= mn;
32        cnt++;  // 操作计数
33    }
34    
35    // 输出答案
36    printf("%d\n", cnt);
37    return 0;
38}

代码说明：

• 每次寻找最大值时，我们使用 >= 比较，这样可以保证当多个最大值存在时，最终保留的是下标最大的那个。
• 在寻找最小值时，mn 的初值设为 a[mx] 是安全的，因为如果数组中有更小的非零数，它一定会被更新；如果没有，说明所有非零数都相等，mn 就等于那个值。
• 循环退出条件检查 a[mx] == 0，因为如果最大值都是 $0$，数组必然全零。

时间复杂度分析

设 $S = \sum a_i$，即初始数组所有元素之和。

• 每次操作至少使 $S$ 减少 $1$，因此操作次数上界为 $S \le 10000$。
• 每次操作需要 $O(n)$ 时间扫描数组（寻找最大值和最小值）。
• 总时间复杂度 $O(n \cdot S)$，在最坏情况下约为 $100 \times 10000 = 10^6$，完全可以接受。

空间复杂度仅为 $O(n)$，存储数组。

---

这道题的难点在于准确理解操作规则，并意识到在数据范围下直接模拟是足够高效的做法。希望本题解能帮助你理解整个过程。