求解成本约束下数组全元素归零的最少合法操作步数

首先修正题目翻译歧义：若按原文字面意思将操作后剩余值的和作为成本，选x等于当前数组最大值时成本恒为0，阈值K完全不生效，不符合算法题考察逻辑。结合问题背景，实际规则为单次操作成本是所有元素被减去的数值总和，即选x后所有≥x的元素各减x，总减去的数值和不能超过K，要求用最少合法操作把所有元素变为0。
该问题完全不需要高复杂度的动态规划，用贪心+后缀预处理即可做到O(N + 10^5)的时间复杂度，轻松覆盖1e5规模的约束。 #

核心逻辑 #

1. 成本单调性：选的x越小，被操作覆盖的元素越多，操作成本越高；x越大，覆盖元素越少，成本越低。要让步数最少，每一步必须在成本不超过K的前提下选最小的合法x，让单次操作减去的总数值尽可能多，最快降低数组整体数值。
2. 成本快速计算：通过预处理后缀计数数组，可以O(1)得到任意高度对应的操作成本，不需要每次操作遍历整个数组。
3. 层打包贪心：我们可以把数组看成直方图，每个高度为1的水平层对应的操作成本等于该高度及以上的元素总个数（每削掉这一层，每个覆盖到的元素都要减1，总成本就是元素数）。我们从最高层往低层遍历，把连续的、总成本不超过K的层打包到同一次操作里，就能得到最少步数。

具体实现步骤 #

1. 预处理计数数组
   因为元素值上限是1e5，直接开长度为100002的计数数组cnt，遍历原数组统计每个值出现的次数，即cnt[v]表示值为v的元素总个数。
2. 从高到低贪心打包层
   初始化三个变量：
   • now_cnt = 0：当前已经遍历到的、待打包的元素总个数
   • now_cost = 0：当前打包的层累计总成本
   • res = 0：总操作步数
     从最大可能值100000倒序遍历到1：
   • 先把当前高度的元素数加到now_cnt里：now_cnt += cnt[i]
   • 如果now_cnt == 0，说明当前高度没有元素，直接跳过
   • 把当前高度这一层的成本加到累计成本里：now_cost += now_cnt（每削1层，每个覆盖元素贡献1点成本）
   • 如果now_cost > K，说明当前层加进去就超过成本阈值了，必须新开一次操作：总步数加1，把当前层的成本作为新操作的初始成本，即res +=1; now_cost = now_cnt
     遍历完所有高度后，如果now_cost > 0，说明最后还有不足K的剩余层需要一次操作，总步数再加1。

复杂度说明 #

整个流程只需要遍历一次数组做计数，再遍历一次1e5的高度范围，总时间复杂度为O(N + 1e5)，空间复杂度为O(1e5)，在题目约束下运行速度极快，完全不会超时。

内容的提问来源于stack exchange，提问作者Himanshu Kaushik