[USACO24OPEN] Cowreography G

_H17_ · 2025-08-21 18:35:21 · 题解

前言

非常好，肥肠有意思的神秘贪心题！！！

题目分析

我们假设两个字符串分别是 a,b。

我们把点分成 3 类：对于 i，如果 a_i=\texttt{0},b_i=\texttt{1}，这是第 1 类点；如果 a_i=\texttt{1},b_i=\texttt{0}，这是第 0 类点；其他点是 2 类点。

我们需要把一个 0 类点和一个 1 类点匹配，使得步数最小。对于 2 类点，显然不动最优。

考虑两个点分别为 i,j(i<j)，两者是不同类型的非 2 类点。通过交换把他们换成 2 类点的步数是 \lceil\frac{j-i}{k}\rceil（每次只能换 k，所以现需要这么多步）。

对于 0\le a,b\le 1,a\ne b 的 a,b，假设当前有 x 个 a 类点没有匹配，遇到了一个 b 类点。如果不考虑向上取整那选哪一个 a 类点答案都一样，因为之后（包括当前）的 x 个 b 类点都会和 a 匹配，顺序和答案无关，答案是这些 b 的下标和减去 a 的下标和。而且同时此时不选取前面的 a 类点一定不优，因为会多算两次这个点和后面一个 a 类点之间的距离。

由于有向上取整，我们尽量选取这些 a 中差是 k 倍数的，如果没有的话选择的余数最大的，因为我们希望浪费的步数尽量小。

为什么加入向上取整之后不会影响一开始的策略？违反一开始的策略至少会多走 2，而这里的取整影响一定更少。

可以使用 set 维护这里的点。

时间复杂度 O(n\log n)。