GESP 题解库 / 3 级题解 / [GESP202509 三级] 数组清零 · 第 5 / 28 题
GESP202509 三级 · B4413 · 入门

数组清零

反复执行"最大值减去最小非零值",问多少次操作后数组全变成 0。n ≤ 100、aᵢ ≤ 100。

📊
n ≤ 100
数据规模
🔢
aᵢ ≤ 100
数值范围
⚡
O(次数 × n)
时间复杂度
🎯
纯模拟
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

给定 n 个非负整数。重复以下操作直到全部为 0:

  1. 找到最大的整数,记下标为 k(若有多个最大值,取下标最大的那个)
  2. 在所有非零整数中找到最小的整数 aⱼ
  3. 把 aₖ 减去 aⱼ

例如 [2, 3, 4] 需要 7 次操作变成 [0, 0, 0]。求操作次数。

💡
人话翻译:题目已经把规则说得非常清楚了,而且数据范围极小(n ≤ 100,每个数 ≤ 100),所以不需要找规律,照着规则老实模拟就行。这正是这道题的考点:把文字规则准确翻译成代码。

🔍 关键词提取

规则模拟找最大值找最小非零值while 循环

已知条件

项目说明
输入第一行 n;第二行 n 个非负整数
输出全部变成 0 所需的操作次数
数据范围1 ≤ n ≤ 100,0 ≤ aᵢ ≤ 100
多解处理多个最大值时取下标最大的
终止保证题目说明必然能在有限次后全部归零

需要解决的问题

02
思维导图
整理解题思路的全貌
🔁 三条规则 + 一个计数
📥 读入
n 和数组 a
计数器 cnt = 0
总和 sum 用来判终止
注意 0 要排除在最小值候选外
🔍 找两个位置
找最大值(下标最大)
找最小非零值
两个都要扫一遍
都是 O(n)
➖ 执行减法
a[k] 减去 a[j]
cnt 加 1
可能变成 0 也可能还是正数
再回到循环开头
⛔ 终止条件
全部元素都是 0
等价于总和为 0
每次至少减 1
最多 10⁴ 次
03
样例手算推导
亲手把 [2, 3, 4] 和 [1, 3, 2, 2, 5] 模拟一遍

🧮 样例 1:[2, 3, 4],答案 7

题面已经给出了变化过程,我们把它拆解成"每一步选了什么"。

第几步数组状态最大值(下标最大)最小非零值减法动作
初始[2, 3, 4]———
1[2, 3, 2]4(下标 3)24 − 2 = 2
2[2, 1, 2]3(下标 2)23 − 2 = 1
3[2, 1, 1]2(下标 3)12 − 1 = 1
4[1, 1, 1]2(下标 1)12 − 1 = 1
5[1, 1, 0]1(下标 3)11 − 1 = 0
6[1, 0, 0]1(下标 2)11 − 1 = 0
7[0, 0, 0]1(下标 1)11 − 1 = 0
🔑
注意第 1 步:数组里只有一个 4,所以最大值下标是 3;而最小非零值是 2(下标 1 或 3),不是 0 —— 如果把 0 也算进最小值,减法就变成"什么都不减",程序会死循环。

🧮 样例 2:[1, 3, 2, 2, 5],答案 13

这组数据更细致地考察"多个最大值 + 下标最大"和"最小非零值是 1"的情形。

1
最小值一直是 1

只要数组里还有 1,最小非零值就是 1

每一次操作都相当于"最大值 − 1"

所以数组会缓慢地逐个归零

2
中间几步的关键选择

第 3 步时数组为 [1, 3, 2, 2, 3],最大值 3 出现在下标 2 和下标 5

按规则取下标最大的 → 选下标 5

所以变成 [1, 3, 2, 2, 2]

✅ 这一步区分了对错解法

3
收尾阶段

当数组变成 [1, 1, 1, 1, 1] 后,

每次操作会让下标最大的那个 1 变成 0

5 个 1 需要 5 步全部清零

✅ 累计共 13 步

阶段数组状态说明
初始[1, 3, 2, 2, 5]
第 1 ~ 4 步[1, 3, 2, 2, 4] → [1, 3, 2, 2, 3] → [1, 3, 2, 2, 2] → [1, 2, 2, 2, 2]最大值一路减 1
第 5 ~ 8 步[1, 2, 2, 2, 1] → [1, 2, 2, 1, 1] → [1, 2, 1, 1, 1] → [1, 1, 1, 1, 1]注意下标最大的先被减
第 9 ~ 13 步[1, 1, 1, 1, 0] → [1, 1, 1, 0, 0] → [1, 1, 0, 0, 0] → [1, 0, 0, 0, 0] → [0, 0, 0, 0, 0]逐个清零
🔑
为什么这题不用找数学规律?数据范围小到可以硬模拟(最多约 10⁴ 次操作 × 100 个数 = 10⁶ 次判断),而且规则里的"下标最大"这类细节用公式很难直接表达。模拟是唯一稳妥的选择。
04
解法对比
模拟法 vs 数学规律法

⚔️ 解法对比

🟢 纯模拟(推荐) 推荐

照着三步规则循环执行,直到总和为 0

  • 最坏约 10⁶ 次操作
  • 代码直接对应题面,不易错
  • 不用推导任何公式
  • n、aᵢ 范围小,稳过
💡
为什么够用:操作次数上界是"总和"(≤ 10⁴),每次操作扫两遍数组 O(n),总计 10⁶ 量级,一眨眼就跑完。

🟠 找数学规律

有人会想:这和"更相减损术"有关吗?能否用 gcd 直接算?

  • 本题的规则带"下标最大"约束
  • 只对部分数据成立
  • 公式难以覆盖所有情况
  • 风险高、收益低
⚠️
结论:这题确实有更相减损术的影子(每次减最小非零值),但"取下标最大的最大值"让规律变得复杂,不值得为此冒险。

📈 性能对比

方案运算量推荐度
纯模拟约 10⁶ 次⭐⭐⭐⭐⭐
数学规律约 10² 次⭐⭐(易错)
05
算法流程图
while 循环 + 三步操作
开始读入 n 和数组 a;cnt = 0数组里还有非零元素吗?找到最大值(下标最大的那个)在所有非零元素中找到最小值a[k] 减去 a[j],cnt 加 1输出 cnt结束还有非零 → 继续一轮操作
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🔁 数组清零模拟器

输入数组(空格分隔),程序会按规则逐步模拟,并显示每一步的数组状态。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码

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

int a[105];

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);

    long long cnt = 0;
    while (true) {
        // 判断是否已经全部为 0
        bool allZero = true;
        for (int i = 0; i < n; i++) if (a[i] != 0) { allZero = false; break; }
        if (allZero) break;

        // ① 找最大值,下标要取最大的(用 >= 才能取到更靠后的)
        int k = 0;
        for (int i = 0; i < n; i++) if (a[i] >= a[k]) k = i;

        // ② 在所有非零元素中找最小值
        int j = -1;
        for (int i = 0; i < n; i++)
            if (a[i] > 0 && (j == -1 || a[i] < a[j])) j = i;

        // ③ 相减并计数
        a[k] -= a[j];
        cnt++;
    }

    printf("%lld\n", cnt);
    return 0;
}
🔑
两个容易写错的细节:① 找最大值时用 >= 而不是 > —— 这样遇到相同的最大值会自动取到更靠后的下标,正好符合题意;② 找最小值时必须加 a[i] > 0 的条件,把 0 排除在外。

📖 关键几行怎么看

代码作用为什么这样写
if (a[i] != 0) allZero = false;判断是否全部归零只要有一个非零就继续循环
if (a[i] >= a[k]) k = i;取下标最大的最大值>= 是本题的关键细节
a[i] > 0 && ...排除 0最小非零值不能是 0,否则死循环
long long cnt计数本题最多约 10⁴ 次,int 也够,写 long long 更保险
⚠️
死循环陷阱:如果找最小值时忘了排除 0,当数组里还有非零元素但最小值是 0 时,减法相当于没减,循环永远不结束。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
3
2 3 4
7题面样例 1
5
1 3 2 2 5
13题面样例 2,考察下标最大的最大值
1
0
0已经是全 0,一次都不用做
1
5
1单个元素:5 − 5 = 0
2
2 2
2两个相同值:各减一次 2
2
1 1
2最小值恒为 1,逐个清零
✅
自查清单:① 最小值是否排除了 0?② 最大值是否用了 >=?③ 终止条件是不是"全部为 0"?

🚨 易错点清单

⚠️
找最小值时没排除 0:会导致减法无效、程序死循环。
⚠️
找最大值时用了严格大于:写成 > 会取到第一个最大值,而题目要求取最后一个,结果会偏大或偏小。
⚠️
先做减法再找最小值:三步必须按顺序执行,如果先把 aₖ 改小,可能会改变"最小值是谁"的判断。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(次数 × n)
空间复杂度
O(n)
最坏次数
约 10⁴
最坏运算
约 10⁶

时间怎么算的?

空间都用在哪?

只需要一个长度 n 的数组保存当前状态,n ≤ 100。

✅ 最坏 10⁶ 次操作,C++ 几毫秒内完成,模拟法完全够用。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 更相减损术:求最大公约数的"减法版"
int gcdBySub(int a, int b) {
    while (a != b) {
        if (a > b) a -= b; else b -= a;
    }
    return a;
}

// 数组的"全部归零"判断可以简写成总和判断
int sum = 0;
for (int i = 0; i < n; i++) sum += a[i];
// 只要 sum > 0 就继续

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
规则模拟把文字描述的三步准确翻译成代码所有"操作流程"类题目
找最大/最小值一次遍历同时记录值和下标数组处理、统计题
while + 终止判断用"总和是否为 0"控制循环模拟类、博弈类题目
🌟
思考题:如果把规则改成"每次都减去最小非零值,但只对最大值操作一次",结果会不会不同?(提示:当有多个相同的最大值时,题目要求只减其中一个,这和"把所有最大值都减一遍"是不同的。)