解题思路
将商品按余数 r=aimodk 分桶。结对规则只取决于余数:
- 余数为 0 的商品可以同类两两结对;若 k 为偶数,余数为 k/2 的商品同样可以同类两两结对。这类桶最终最多留下
1 件。为使剩余和最大,应撤下该桶中最小的 2⌊∣Vr∣/2⌋ 件。
- 对于互补余数对 r 与 s=(k−r)modk(1≤r<s≤k−1):两类之间可以跨类结对,最终至少有一类会被清空,因此必须从两侧各撤下 m=min(∣Vr∣,∣Vs∣) 件。为使剩余和最大,两侧都撤下最小的 m 件。
每个桶升序排序并做前缀和后,O(1) 求出应撤下的体积和。没有互补桶的余数则全部保留。