题解

题目解析

• 输入输出：第一行输入整数 $n$ 表示数组长度，第二行输入 $n$ 个非负整数。输出将整个数组清零所需的操作次数。
• 数据范围：$1 \le n \le 100$，$0 \le a_i \le 100$。数据规模较小，允许使用带排序的模拟方法。
• 复杂度要求：由于 $a_i \le 100$ 且每次操作至少将某个正整数减少或消除，总操作次数上限为 $O(n \cdot \log(\max(a_i)))$ 级别；每次排序 $O(n \log n)$，总复杂度约为 $O(n^2 \log n \cdot \log(\max(a_i)))$，在 $n=100$ 范围内可接受。
• 算法知识点：模拟、排序、贪心、数组处理

思路解析

1. 操作的本质：每次操作需找到当前数组中的最大值（若有多个取最大下标）和最小非零值，并将最大值减去该最小值。这等价于：将数组降序排序后，用首元素（最大）减去尾元素（最小非零）。
2. 维护有序性：每次操作后，被修改的最大值可能不再最大，因此需要重新排序，确保下一次循环时 arr.front() 仍是当前最大值，arr.back() 是当前最小值（非零）。
3. 零值处理：在每次操作前，通过内层 while 循环弹出数组末尾的所有 $0$，确保 arr.back() 始终是非零最小值（或数组为空）。
4. 计数技巧：变量 ans 初始化为 $-1$，是因为循环体执行次数（包括最后清理剩余 $0$ 的那次循环）比实际"减法操作"次数多 $1$；通过初始 $-1$ 的偏移，最终恰好得到正确的操作次数。
5. 终止条件：当数组中所有元素都变为 $0$ 并被弹出后，数组为空，循环结束。

完整代码

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

int main() {
    int n;
    cin >> n;
    vector<int> arr(n);
    for(int i = 0; i < n; i++) cin >> arr[i];
    
    int ans = -1;  // 初始化-1用于最后抵消多余的循环计数
    // 降序排序：front为最大值，back为最小值（非零时）
    sort(arr.begin(), arr.end(), greater<int>());
    
    while(!arr.empty()) {
        // 关键：移除所有末尾的0，确保back()是最小非零值
        while(!arr.back() && !arr.empty()) arr.pop_back();
        
        // 如果数组已空（全为0），避免访问越界（实际数据可能保证此处非空）
        if(arr.empty()) break;
        
        // 关键：执行操作——最大值减去最小值
        arr.front() -= arr.back();
        
        // 重新排序，维护有序性以便下一次操作
        sort(arr.begin(), arr.end(), greater<int>());
        ans++;
    }
    cout << ans << endl;
    return 0;
}