Codeforces999 D. Equalize the Remainders

给 $n$ 个数和一个 $k$,把$n$个数按 % $k$ 的余数,分成 $m$ 组 ( 即每组的余数为 $[0 , m-1]$ ) ,使得每组数的个数都相等。我们一次操作:可以任选某个数,把它的值 $+1$。 问操作的最小次数和操作后的序列。($n < 2·1e5,m<n$)


自己用set 贪心模拟,成功得出最优解,但因各种迭代器访问,以及很多$erase (log)$,T掉了,写的也很混乱,记录方案也很是愚蠢 $==$

题解

因为只能增大,一个显然的做法是可以强行的从小到大,把多的压到下一个,直至所有数都为$\frac{n}{m}$,但是很不幸,这道题要求输出操作后的序列,所以我们要记录每个数的位置,故这样做是不行的,因为最坏情况下一开始全部余数为 $0$ ,复杂度为 $O(n*m)$

你会发现有很多的操作是没有用的,比如一开始全部余数为 $0$,将 $n-\frac{n}{m}$ 有 $n-2*\frac{n}{m}$ 是没用的,
在这整道题中,有一个性质很容易看出,
从余数小的变为大的,可以直接递推过去,
但余数大的变为小的,就要优先的把最大的变为小的,因为这样是最优的

一个很优秀的做法

第一次直接从左往右递推过去,左边有多的就直接给右边的。
但这样肯定存在没有处理的位置,所以剩下没处理的位置,肯定是需要先变为$m-1$再变成需要的数

Trick:注意$vector$为空,不能再访问其中元素