题目解析
* 输入输出:第一行输入整数 nnn 表示数组长度,第二行输入 nnn 个非负整数。输出将整个数组清零所需的操作次数。
* 数据范围:1≤n≤1001 \le n \le 1001≤n≤100,0≤ai≤1000 \le a_i \le 1000≤ai ≤100。数据规模较小,允许使用带排序的模拟方法。
* 复杂度要求:由于 ai≤100a_i \le 100ai ≤100 且每次操作至少将某个正整数减少或消除,总操作次数上限为 O(n⋅log(max(ai)))O(n \cdot \log(\max(a_i)))O(n⋅log(max(ai ))) 级别;每次排序 O(nlogn)O(n \log n)O(nlogn),总复杂度约为 O(n2logn⋅log(max(ai)))O(n^2 \log n \cdot \log(\max(a_i)))O(n2logn⋅log(max(ai ))),在 n=100n=100n=100 范围内可接受。
* 算法知识点:模拟、排序、贪心、数组处理
思路解析
1. 操作的本质:每次操作需找到当前数组中的最大值(若有多个取最大下标)和最小非零值,并将最大值减去该最小值。这等价于:将数组降序排序后,用首元素(最大)减去尾元素(最小非零)。
2. 维护有序性:每次操作后,被修改的最大值可能不再最大,因此需要重新排序,确保下一次循环时 arr.front() 仍是当前最大值,arr.back() 是当前最小值(非零)。
3. 零值处理:在每次操作前,通过内层 while 循环弹出数组末尾的所有 000,确保 arr.back() 始终是非零最小值(或数组为空)。
4. 计数技巧:变量 ans 初始化为 −1-1−1,是因为循环体执行次数(包括最后清理剩余 000 的那次循环)比实际"减法操作"次数多 111;通过初始 −1-1−1 的偏移,最终恰好得到正确的操作次数。
5. 终止条件:当数组中所有元素都变为 000 并被弹出后,数组为空,循环结束。
完整代码