记录编号	596196	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[USACO24 Open Gold]Cowreography	最终得分	100
用户昵称	yuan	是否通过	通过
代码语言	C++	运行时间	1.216 s
提交时间	2024-10-23 12:42:03	内存使用	4.68 MiB

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;

int main() {
	freopen("cowreography.in","r",stdin);        
	freopen("cowreography.out","w",stdout); 
	cin.tie(0)->sync_with_stdio(0);
	int n, k;
	cin >> n >> k;
	string s1, s2;
	cin >> s1 >> s2;
	
	ll ans = 0;
	map<int, int> mismatches;
	for (int i = 0; i < n; i++) {
		int d = s1[i] - s2[i];  // d = 0 if match; +1 if 0|1; -1 if 1|0
		
		// 首先，将扫描线之前的任何不匹配项向前移动
		// 并相应地增加答案
		while (mismatches.size() && mismatches.begin()->first < i) {
			pair<int, int> curr = *mismatches.begin();
			mismatches[curr.first + k] += curr.second;
			ans += abs(curr.second);
			mismatches.erase(curr.first);
		}
		// 接下来，解决从当前位置可到达的任何不匹配项
		if (mismatches.size() && mismatches.begin()->second * d < 0) {
			mismatches.begin()->second += d;
			if (mismatches.begin()->second == 0)
				mismatches.erase(mismatches.begin());
		} else if (d)
			mismatches[i] += d;
	}
	
	cout << ans << '\n';
	return 0;
}