[USACO24OPEN] Cowreography G

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

我们假设两个字符串分别是 $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)$。