反复执行"最大值减去最小非零值",问多少次操作后数组全变成 0。n ≤ 100、aᵢ ≤ 100。
给定 n 个非负整数。重复以下操作直到全部为 0:
例如 [2, 3, 4] 需要 7 次操作变成 [0, 0, 0]。求操作次数。
规则模拟找最大值找最小非零值while 循环
| 项目 | 说明 |
|---|---|
| 输入 | 第一行 n;第二行 n 个非负整数 |
| 输出 | 全部变成 0 所需的操作次数 |
| 数据范围 | 1 ≤ n ≤ 100,0 ≤ aᵢ ≤ 100 |
| 多解处理 | 多个最大值时取下标最大的 |
| 终止保证 | 题目说明必然能在有限次后全部归零 |
题面已经给出了变化过程,我们把它拆解成"每一步选了什么"。
| 第几步 | 数组状态 | 最大值(下标最大) | 最小非零值 | 减法动作 |
|---|---|---|---|---|
| 初始 | [2, 3, 4] | — | — | — |
| 1 | [2, 3, 2] | 4(下标 3) | 2 | 4 − 2 = 2 |
| 2 | [2, 1, 2] | 3(下标 2) | 2 | 3 − 2 = 1 |
| 3 | [2, 1, 1] | 2(下标 3) | 1 | 2 − 1 = 1 |
| 4 | [1, 1, 1] | 2(下标 1) | 1 | 2 − 1 = 1 |
| 5 | [1, 1, 0] | 1(下标 3) | 1 | 1 − 1 = 0 |
| 6 | [1, 0, 0] | 1(下标 2) | 1 | 1 − 1 = 0 |
| 7 | [0, 0, 0] | 1(下标 1) | 1 | 1 − 1 = 0 |
这组数据更细致地考察"多个最大值 + 下标最大"和"最小非零值是 1"的情形。
只要数组里还有 1,最小非零值就是 1
每一次操作都相当于"最大值 − 1"
所以数组会缓慢地逐个归零
第 3 步时数组为 [1, 3, 2, 2, 3],最大值 3 出现在下标 2 和下标 5
按规则取下标最大的 → 选下标 5
所以变成 [1, 3, 2, 2, 2]
✅ 这一步区分了对错解法
当数组变成 [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] | 逐个清零 |
照着三步规则循环执行,直到总和为 0
有人会想:这和"更相减损术"有关吗?能否用 gcd 直接算?
| 方案 | 运算量 | 推荐度 |
|---|---|---|
| 纯模拟 | 约 10⁶ 次 | ⭐⭐⭐⭐⭐ |
| 数学规律 | 约 10² 次 | ⭐⭐(易错) |
输入数组(空格分隔),程序会按规则逐步模拟,并显示每一步的数组状态。
点按钮开始 →
#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 更保险 |
写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
3 | 7 | 题面样例 1 |
5 | 13 | 题面样例 2,考察下标最大的最大值 |
1 | 0 | 已经是全 0,一次都不用做 |
1 | 1 | 单个元素:5 − 5 = 0 |
2 | 2 | 两个相同值:各减一次 2 |
2 | 2 | 最小值恒为 1,逐个清零 |
> 会取到第一个最大值,而题目要求取最后一个,结果会偏大或偏小。只需要一个长度 n 的数组保存当前状态,n ≤ 100。
✅ 最坏 10⁶ 次操作,C++ 几毫秒内完成,模拟法完全够用。
// 更相减损术:求最大公约数的"减法版" 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"控制循环 | 模拟类、博弈类题目 |