📝 题目大意

给定 $N$ 个正整数，每次操作将数组降序排序后将前两个最大元素各减 $1$，直到数组中正整数的个数不超过 $1$ 为止。求操作的总次数。

💡 解题思路

1. 题目分析：数据范围很小（$N \leq 100$，$A_i \leq 100$），直接模拟即可。每次操作会使数组元素总和减少 $2$，而总和有上界 $N \times 100 \leq 10000$，因此操作次数最多约 $5000$ 次，模拟完全可行。

2. 算法推导：

   • 每轮操作前，将数组 $a[1 \ldots N]$ 按降序排序，确保 $a[1]$ 和 $a[2]$ 是当前最大的两个元素。
   • 将 $a[1]$ 和 $a[2]$ 各减 $1$。
   • 统计数组中正整数的个数 cnt（即 $a[i] > 0$ 的元素数）。
   • 操作计数器 ans 加 $1$。
   • 若 cnt < 2（即正整数的个数 $\leq 1$），则终止循环；否则继续下一轮。
   • 最终输出 ans。

   正确性说明：每次操作严格按照题意——先降序排序，再对前两个元素各减 $1$。由于每次操作必然减少数组中两个元素的值，且元素值非负，总操作次数有限，循环必然终止。终止条件 cnt < 2 等价于"正整数的个数为 $0$ 或 $1$"，与题目要求一致。

3. 边界与细节：

   • 数组排序使用自定义比较函数 cmp 实现降序（return a > b），注意 sort 的区间是左闭右开 $[1, N+1)$。
   • 即使 $a[1]$ 或 $a[2]$ 在操作前已经是 $0$，也照常减 $1$（变为负数），但这不影响后续判断，因为正整数的计数只看 $a[i] > 0$。
   • 判断 cnt < 2 放在 ans++ 之后，确保最后一次将正数个数降至 $1$ 或 $0$ 的操作也被计入，与题目示例一致。

⏱️ 复杂度分析

• 时间复杂度：每次循环需要 $O(N \log N)$ 排序，循环次数最多约 $\frac{\sum A_i}{2} \leq 5000$ 次。总复杂度 $O(N \cdot \sum A_i \cdot \log N)$，在 $N=100$ 时约 $10^5$ 级别，远小于时限。
• 空间复杂度：仅需一个长度为 $N+5$ 的数组存储元素，$O(N)$。

💻 标准代码 (C++)

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

// 自定义降序比较函数
bool cmp(int a, int b) {
    return a > b;
}

int main() {
    int n, a[105], ans = 0;   // a 数组下标从 1 开始，预留足够空间
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);  // 读入 N 个正整数
    while (true) {
        sort(a + 1, a + n + 1, cmp);  // 按降序排序
        a[1]--, a[2]--;                // 对最大的两个元素各减 1
        int cnt = 0;
        for (int i = 1; i <= n; i++) {
            if (a[i] > 0) cnt++;       // 统计剩余正整数的个数
        }
        ans++;                         // 操作次数 +1
        if (cnt < 2) break;            // 正数个数 ≤ 1 时停止
    }
    printf("%d", ans);                 // 输出答案
    return 0;
}