思路

• 将数组按余数分组：对每个数计算 $r = a_i \bmod k$，分类到 $V_r$。

• 对于 $r = 0$ 以及（若 $k$ 为偶数）$r = \frac{k}{2}$：同类元素可以两两配对移除，最多只能留下 $1$ 个。要最大化剩余和，应移除该类中最小的 $2 \left\lfloor \frac{|V_r|}{2} \right\rfloor$ 个元素。

• 对于互补余数对 $r$ 与 $s = (k-r) \bmod k$（取 $1 \le r < s \le k-1$）：

  • 最终必须让两类中至少有一类变为空，因此必然会从两边各移除 $m = \min(|V_r|, |V_s|)$ 个元素。
  • 为使剩余和最大，移除两侧中最小的 $m$ 个元素（总移除和最小）。
  • 余下的就是较大一侧的剩余元素（或两边都空）。

• 将每个 $V_r$ 升序排序并做前缀和 $P_r$。记 $\text{sum}(V_r) = P_r[|V_r|]$。

题目内容

给定一个长度为$n$的正整数数组{$a_1,a_2,...,a_n$}，以及一个正整数$k$。 定义一次操作如下: