P10280 [USACO24OPEN] Cowreography G 题解

Description

奶牛们组了一支舞蹈队，Farmer John 是她们的编舞！舞蹈队最新而最精彩的舞蹈有 $N$ 头奶牛（$2\le N\le 10^6$）排成一行。舞蹈中的每次动作都涉及两头奶牛，至多相距 $K$ 个位置（$1\le K < N$），优雅地跳起并降落在对方的位置上。

队伍中有两种奶牛——更赛牛（Guernsey）和荷斯坦牛（Holstein）。因此，Farmer John 将这一舞蹈记录为一系列长为 $N$ 的 01 字符串，其中 0 代表更赛牛，1 代表荷斯坦牛，整个字符串表示奶牛在这一行中是如何排列的。

不幸的是，Farmer Nhoj（对手团队的编舞）蓄意破坏了这一舞蹈，并清除了除第一个和最后一个 01 字符串之外的所有内容！由于一场大型比赛即将开始，Farmer John 必须抓紧每一秒重建这一舞蹈。

给定这两个 01 字符串，帮助 Farmer John 求出舞蹈中的最小动作数量！

Solution

考虑交换一对 $i,j(a_i\neq a_j)$ 所用的代价，结论是 $\left\lceil\frac{|i-j|}{k}\right\rceil$。

证明就考虑数学归纳法，不妨设 $i<j$ 且长度小于 $j-i$ 的已经满足结论，容易发现对于 $j-i\leq k$ 的 $(i,j)$ 一定满足条件。

对于 $i<s<j$，如果 $a_i=a_s$ 则先交换 $(j,s)$ 再交换 $(i,s)$，否则先交换 $(i,s)$ 在交换 $(j,s)$，对应的代价为 $\left\lceil\frac{s-i}{k}\right\rceil+\left\lceil\frac{j-s}{k}\right\rceil$，容易发现当 $s$ 取 $i+k$ 时可以取到最小值，即为 $\left\lceil\frac{|i-j|}{k}\right\rceil$。

有了这个结论就可发现这里的交换一定是两两匹配，即在一张二分图上匹配。

如果没有取上整就从前往后扫，如果 $a_i\neq b_i$ 就找到任意一个还没匹配的 $j$ 使得 $a_i\neq a_j$ 匹配，容易发现这个一定是最小值。

如果有了取上整，感性理解可以发现这里需要让 $(i-j)\bmod k$ 的和尽可能小，所以只要把上面选任意一个匹配变为选使得 $(i-j)\bmod k$ 最小的 $j$ 匹配即可。

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

Code

#include <bits/stdc++.h>

// #define int int64_t

int n, k;
std::string a, b;

void dickdreamer() {
  std::cin >> n >> k >> a >> b;
  a = " " + a, b = " " + b;
  std::set<std::pair<int, int>> st[2];
  int64_t ans = 0;
  for (int i = 1; i <= n; ++i) {
    if (a[i] == b[i]) continue;
    int oa = a[i] - '0', ob = b[i] - '0';
    if (!st[ob].empty()) {
      auto it = st[ob].lower_bound({i % k, 0});
      if (it == st[ob].end()) it = st[ob].begin();
      ans += (i - it->second + k - 1) / k;
      st[ob].erase(it);
    } else {
      st[oa].emplace(i % k, i);
    }
  }
  std::cout << ans << '\n';
}

int32_t main() {
#ifdef ORZXKR
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  int T = 1;
  // std::cin >> T;
  while (T--) dickdreamer();
  // std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
  return 0;
}