【题解】P10280 [USACO24OPEN] Cowreography G
hejianxing
·
·
题解
link
题意
给定两个 01 串，每次操作可以将距离不超过 k 的两个字符交换，求 s\to t 的最小步数。
# 题解
考虑交换两个数，步数显然为 $\lceil\frac{y-x}{k}\rceil$。若没有取整，那么直接顺着扫过去，找到前后不一样的贪心选取即可，即每找到一个不一样的就马上与前面的任意一个交换。
容易感受到需要让取整时补出来的距离尽量少，也就是让每次的 $\lceil\frac{y-x}{k}\rceil k-(y-x)$ 尽量小。
当一个位置为 $i$ 的数需要交换时，选取一个 $j\equiv i\pmod k$ 的数是最优的，$j\equiv i+1\pmod k$ 次之，以此类推。
于是用 `set` 维护等待交换的位置，按 $i\bmod k$ 排序。如果无法交换就把当前位置塞进去。如果可以交换，查找最优的位置是简单的，计算答案也是简单的。
时间复杂度 $O(n\log n)$。
# 实现
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1000005;
int n, k;
LL ans = 0;
char a[N], b[N];
#define mp make_pair
multiset<pair<int, int>> s[2];
int main() {
scanf("%d%d%s%s", &n, &k, a + 1, b + 1);
for (int i = 1; i <= n; i++)
if (a[i] != b[i]) {
int x = a[i] - '0';
if (s[!x].empty()) s[x].insert(mp(i % k, i));
else {
auto it = s[!x].lower_bound(mp(i % k, 0));
if (it == s[!x].end()) it = s[!x].begin();
ans += (i - (it -> second) - 1) / k + 1, s[!x].erase(it);
}
}
printf("%lld\n", ans);
return 0;
}
```