20200305(DEF)题解 by 孙晨曦

今天的D题题解,
预处理每个余数i的数量b[i],
因为对ai的操作只能+1,所以第一遍从0到m-1枚举余数,
若b[i]>n/m,只能把b[i]-n/m个数转移到下一个位置上,(最后b[m-1]转移到b[0])
这样枚举两边就是最终结果。
但是如果每次只转移到相邻的下一个位置,2e5个数最多能转移2e5*2e5次就TLE了
所以开一个指针point,指向从i+1到m-1之间第一个b<n/m的位置,然后转移时,把i转移到point就行了
point可以用个while推进,转移可以开m-1个队列维护元素进出

原文地址:https://www.cnblogs.com/QLU-ACM/p/12430875.html