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

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MAXN 1000010
inline ll read(){
	ll x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=x*10+c-'0';
		c=getchar();
	}
	return x*f;
}
ll n,k,ans;
char a[MAXN],b[MAXN];
multiset <pair<ll,ll> > s[5];
int main(){
	freopen("cowreography.in","r",stdin);
	freopen("cowreography.out","w",stdout);
	n=read(),k=read();
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++)cin>>b[i];
	for(int i=1;i<=n;i++){
		if(a[i]==b[i])continue;
		ll x=a[i]-'0';
		if(s[!x].empty())s[x].insert(make_pair(i%k,i));
		else{
			multiset<pair<ll,ll> >::iterator y=s[!x].lower_bound(make_pair(i%k,0));
			if(y==s[!x].end())y=s[!x].begin();
			ans+=(i-(*y).second+k-1)/k;
//			cout<<i<<" "<<(*y).second<<" "<<(i-(*y).second+k-1)/k<<endl;
			s[!x].erase(y);
		}
	}
	cout<<ans;
	return 0;
}