最自然的第一写法是维护一个 hash 集合存“最终已经占用的值”：对每个数，如果冲突就不断做 \(\pm k\)，直到变成没出现过的值再插入。随机数据下这看起来可能挺快，但最坏情况非常糟：如果很多数落在同一条“可达链”（也就是同一个余数类）里，第 \(i\) 次插入可能需要 \(\Theta(i)\) 次重试，于是总重试次数是
\[0+1+\cdots+(n-1)=\Theta(n^2),
\]
赛时直接 TLE。
我们考虑优化，我们需要一个有保证的界。令 \(d=|k|\)。关键不变量是：对任意数 \(a\)，加/减 \(k\) 永远不会改变它对 \(d\) 的余数。因此冲突只可能发生在同一个余数类内部。我们按
\[r \equiv a \pmod d,\qquad r\in{0,1,\dots,d-1}
\]
把所有数分桶。
在一个桶内（固定 \(r\)），每个数都能写成
\[a = r + d\cdot b
\]
其中 \(b\) 是整数。一次操作 \(\pm k\) 等价于 \(b\) 改变 \(\pm 1\)（当 \(k<0\) 时方向相反，用乘 \(\mathrm{sgn}(k)\) 统一即可）。因此每个桶都变成一维问题：给定一堆整数 \(x\)，只允许把它们往上推，使所有值互不相同，并最小化总增量。
桶内做法：把 \(x\) 排序后从左到右扫描，维护 \(\mathrm{prev}\) 为上一个已经确定的值。对每个 \(x\)：
- 若 \(x>\mathrm{prev}\)，保留；
- 否则必须把它提高到 \(\mathrm{prev}+1\)，答案加上 \((\mathrm{prev}+1-x)\)，并令 \(x\leftarrow \mathrm{prev}+1\)。
这是最优的：当 \(x\le \mathrm{prev}\) 时，任何合法的最终值都至少要到 \(\mathrm{prev}+1\)；取 \(\mathrm{prev}+1\) 是当前最小代价，取更大会更亏，而且不会让后面更省。
总复杂度由各桶排序决定，为 \(O(n\log n)\)。
本题解思路为本人赛时解法，文字部分由 AI 协助整理润色。