Round Robin风格大数组递减的高效算法咨询

现有元素规模可达百万级的数组，数组内存储的数值需要执行递减操作，给定递减操作总配额t。要求按照Round Robin（轮询）规则遍历数组执行递减：即从数组头部开始逐个给元素减1，走到数组尾部就回到头部循环，直到配额用完，最终返回所有值被减到0的元素的索引。
常规逐次单步循环执行递减的方案，在大数组、大配额场景下性能极差，需要更高效的实现思路。

参考示例：

t = 30 # 递减总配额
A = [2,4,5,20,10,40,3,8,11,1] # 数组规模最高可达百万级
# 递减完成后数组: [0, 0, 1, 16, 7, 37, 0, 5, 8, 0]
# 返回0值元素索引: [0,1,6,9]

别做单步循环，核心思路是批量计算整轮扣减的消耗，跳过无意义的逐次操作，整体时间复杂度为O(n log n)，百万级数据可以轻松处理，具体步骤如下：

• 先把每个元素的原始值和它的索引绑定，避免后续排序丢失位置信息
• 按元素值从小到大排序，分层计算每一层全量轮询的配额消耗：
  • 初始状态下所有元素都是存活状态（未被减到0），设当前扣减基准值为0，存活元素数为数组长度n
  • 找到当前存活元素里的最小值，计算它和当前基准值的差值delta，这时候如果给所有存活元素统一扣delta，需要消耗的配额是delta * 当前存活元素数
  • 如果剩余配额t足够覆盖这部分消耗：直接扣减对应配额，把基准值更新为当前最小值，把所有值等于基准值的元素标记为0，从存活集合中移除，重复这一步计算下一层
  • 如果剩余配额t不够覆盖全量扣减的消耗：先算能完整跑完的轮数full_round = t // 当前存活元素数，把基准值加上full_round，剩下的余数rem = t % 当前存活元素数就是最后一轮从数组头部开始，能额外扣减1的元素个数，这些元素里值等于基准值 + 1的也会被减到0
• 最后收集所有值小于等于最终截止阈值的元素对应的原始索引，就是要求的结果。

拿示例数据走一遍流程验证：
示例数组排序后（值+原索引）为(1,9)、(2,0)、(3,6)、(4,1)、(5,2)、(8,7)、(10,4)、(11,8)、(20,3)、(40,5)，初始基准值prev=0，存活数=10，t=30

1. 当前层最小值1，delta=1-0=1，全量扣减需要1*10=10配额，t=30足够支付，扣完t=20，prev=1，移除值为1的元素（索引9），存活数变为9
2. 下一层最小值2，delta=2-1=1，全量扣减需要1*9=9配额，t=20足够支付，扣完t=11，prev=2，移除值为2的元素（索引0），存活数变为8
3. 下一层最小值3，delta=3-2=1，全量扣减需要1*8=8配额，t=11足够支付，扣完t=3，prev=3，移除值为3的元素（索引6），存活数变为7
4. 下一层最小值4，delta=4-3=1，全量扣减需要1*7=7配额，当前剩余t=3不够支付，停止全量计算
5. 计算剩余配额：full_round=3//7=0，余数rem=3，也就是最后一轮从头开始数3个存活元素（按原数组顺序的存活元素是索引1、2、7、4、8、3、5，前3个是1、2、7），其中值等于prev+1=4的只有索引1，所以索引1也会被减到0
6. 最终收集到的0值索引为0、1、6、9，和示例结果完全匹配。

• 单步循环方案时间复杂度是O(t)，如果t达到千万、亿级，运算耗时会达到秒级甚至分钟级，完全无法适配大场景
• 批量计算方案的耗时主要来自初始排序，时间复杂度O(n log n)，即便是百万级元素的数组，排序耗时也在毫秒级，性能差距可达几个数量级。

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