B4413 [GESP202509 三级] 数组清零

题目描述

小 A 有一个由 $n$ 个非负整数构成的数组 $a=[a_1,a_2,\dots ,a_n]$。他会对阵组 $a$ 重复进行以下操作，直到数组 $a$ 只包含 0。在一次操作中，小 A 会依次完成以下三个步骤：

1. 在数组 $a$ 中找到最大的整数，记其下标为 $k$。如果有多个最大值，那么选择其中下标最大的。
2. 从数组 $a$ 所有不为零的整数中找到最小的整数 $a_j$。
3. 将第一步找出的 $a_k$ 减去 $a_j$。

例如，数组 $a=[2,3,4]$ 需要 7 次操作变成 $[0,0,0]$：

$$[2,3,4]\to [2,3,2]\to [2,1,2]\to [2,1,1]\to [1,1,1]\to [1,1,0]\to [1,0,0]\to [0,0,0]$$

小 A 想知道，对于给定的数组 $a$，需要多少次操作才能使得 $a$ 中的整数全部变成 0。可以证明，$a$ 中整数必然可以在有限次操作后全部变成 0。你能帮他计算出答案吗？

输入格式

第一行，一个正整数 $n$，表示数组 $a$ 的长度。

第二行，$n$ 个非负整数 $a_1,a_2,\dots ,a_n$，表示数组 $a$ 中的整数。

输出格式

一行，一个正整数，表示 $a$ 中整数全部变成 0 所需要的操作次数。

输入输出样例 #1

输入 #1

3
2 3 4

输出 #1

7

输入输出样例 #2

输入 #2

5
1 3 2 2 5

输出 #2

13

说明/提示

对于所有测试点，保证 $1\le n\le 100$，$0\le a_i\le 100$。

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

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

	int ops = 0;

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

		// 1. 找最大值（下标大的优先）
		int maxVal = -1, k = -1;
		for (int i = 0; i < n; i++) {
			if (a[i] > maxVal || (a[i] == maxVal && i > k)) {
				maxVal = a[i];
				k = i;
			}
		}

		// 2. 找最小正数
		int minVal = INT_MAX;
		for (int i = 0; i < n; i++) {
			if (a[i] > 0 && a[i] < minVal) {
				minVal = a[i];
			}
		}

		// 3. 执行减法
		a[k] -= minVal;
		ops++;
	}

	cout << ops << "\n";
	return 0;
}

🧩 一、题目背景

题目大致意思可能是：

给定一个由 n 个非负整数构成的数组 a，每次执行以下操作：

• 找出数组中最大值元素（若有多个，取下标较大的）；
• 找出数组中最小的正整数 minVal；
• 将那个最大值元素减去 minVal；
• 重复此过程，直到所有元素都变为 0。

问：共执行了多少次操作？

🧠 二、整体思路概述

算法的基本逻辑是：

1. 不断模拟题目中的操作；
2. 每次：
   • 找最大值（右边优先）；
   • 找最小正数；
   • 把最大值减去这个最小正数；
   • 操作次数加 1；
3. 当数组全为 0 时停止；
4. 输出操作次数。

🧱 三、代码结构讲解

1️⃣ 输入部分

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

读取数组大小 n；

读取数组 a；

假设 n ≤ 100。

2️⃣ 主循环部分

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

📘 作用：

• 每轮开始前检查数组是否全为 0；
• 如果全是 0，说明操作结束；
• 否则继续下一步。

3️⃣ 找最大值（下标大的优先）

int maxVal = -1, k = -1;
for (int i = 0; i < n; i++) {
	if (a[i] > maxVal || (a[i] == maxVal && i > k)) {
		maxVal = a[i];
		k = i;
	}
}

📘 作用：

• 找出当前数组的最大值及其下标；
• 若有多个最大值，则取下标较大的那个（即靠右的）；
• 记录下标 k 以便后续修改。

4️⃣ 找最小正数

int minVal = INT_MAX;
for (int i = 0; i < n; i++) {
	if (a[i] > 0 && a[i] < minVal) {
		minVal = a[i];
	}
}

📘 作用：

• 找出数组中最小的非零数；
• 因为减 0 没意义，所以只考虑 a[i] > 0；
• 存入 minVal。

5️⃣ 执行一次“操作”

a[k] -= minVal;
ops++;

📘 含义：

• 对最大值位置执行减法；
• 操作次数 ops 自增 1。

6️⃣ 循环结束后输出

cout << ops << "\n";

🧮 四、运行示例

5
2 4 2 6 4

过程如下：

步骤	数组状态	最大值	最小正数	被减位置	新数组	ops
1	2 4 2 6 4	6@3	2	3	2 4 2 4 4	1
2	2 4 2 4 4	4@4	2	4	2 4 2 4 2	2
3	2 4 2 4 2	4@3	2	3	2 4 2 2 2	3
4	2 4 2 2 2	4@1	2	1	2 2 2 2 2	4
5	2 2 2 2 2	2@4	2	4	2 2 2 2 0	5
6	2 2 2 2 0	2@3	2	3	2 2 2 0 0	6
7	2 2 2 0 0	2@2	2	2	2 2 0 0 0	7
8	2 2 0 0 0	2@1	2	1	2 0 0 0 0	8
9	2 0 0 0 0	2@0	2	0	0 0 0 0 0	9

最后输出：

9

⚙️ 五、时间复杂度分析

• 每次循环都要：
  • 扫描一遍判断全 0 → O(n)
  • 扫描一遍找最大值 → O(n)
  • 扫描一遍找最小正数 → O(n)
• 最坏情况下操作次数可能接近每个数被逐步减为 0 的总次数。
• 所以整体复杂度 ≈ O(n × 操作次数)，适合小数据（n ≤ 100）。

✨ 六、总结要点

步骤	目的	关键点
判断全零	判断结束条件	用标志变量 allZero
找最大值	选择被操作元素	同值取右边
找最小正数	决定减多少	跳过 0
执行减法	模拟一次操作	操作数 +1
循环终止	全零时结束	输出总次数

✅ 【优化版代码】

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

int main() {
    int n;
    cin >> n;
    int a[110];
    for (int i = 0; i < n; i++) cin >> a[i];

    int ops = 0;

    while (true) {
        // 找出最小的正整数 minVal
        int minVal = INT_MAX;
        for (int i = 0; i < n; i++) {
            if (a[i] > 0) minVal = min(minVal, a[i]);
        }
        // 若不存在正数（说明全为0），跳出循环
        if (minVal == INT_MAX) break;

        // 找到最大值下标（右边优先）
        int maxPos = -1, maxVal = -1;
        for (int i = 0; i < n; i++) {
            if (a[i] > maxVal || (a[i] == maxVal && i > maxPos)) {
                maxVal = a[i];
                maxPos = i;
            }
        }

        // 执行操作
        a[maxPos] -= minVal;
        ops++;
    }

    cout << ops << "\n";
    return 0;
}

✨ 优化思路讲解

优化点	原因	效果
取消全零判断	全零时自然没有正数，所以 minVal == INT_MAX 可直接退出	减少一次遍历
合并变量查找逻辑	每次只找最小正数一次，不必在循环顶部再全扫一遍	更直观
命名更直白	maxPos、maxVal 语义清晰	更易读

📘 对比总结

项目	原版	优化版
判断全零	单独循环检查	自动通过 minVal 判断
查找逻辑	三次循环	两次循环
性能	O(3n×操作数)	O(2n×操作数)
可读性	稍显繁琐	简洁明了
正确性	✅	✅