题解：P10280 [USACO24OPEN] Cowreography G

Istruggle · 2025-05-20 17:13:57 · 题解

如果交换 a_i 与 a_j 那么贡献为 \left \lceil \frac{j-i}{k} \right \rceil，同时我们有一个结论：如果没有向上取整则 i 与前面任意一个数交换都是最优的，可以理解为答案是 \frac{1}{k} {\textstyle \sum_{i=1}^{n}} \left ( j-i \right ) [s_i\ne s_j] [t_j = s_i] , 这个数值一定是固定的。而有了向上取整后，多出来的贡献其实就是 k\left \lceil \frac{j-i}{k} \right \rceil - j+i , 如果我们想让这个数小就需要在匹配 i 时尽量让 j-i 为 k 的整倍数，因此当 i 需要进行匹配时，就需要在待匹配的数里找到在模 k 下与 i 差最小的 j。这个过程可以用 set 维护。