Codeforces 1037C Equalize 题解

题目描述

给定两个长度为 $n$ 的 $01$ 序列 $a,b$。

每次可以执行如下操作：

1. 在 $a$ 中选择一个位置 $p$，将 $a_p$ 变为 $1-a_p$，代价是 $1$。
2. 在 $a$ 中选择两个位置 $p,q$，将 $a_p$ 和 $a_q$ 互换，代价是 $\lvert q-p \rvert$。

问最少需要多少代价才能将 $a$ 变成 $b$。

题目分析

对于操作二，仅当 $a_q \neq a_p$，$b_q \neq b_p$，并且 $a_q \neq b_q$ 时才能使用，此时代价为 $\lvert q-p \rvert$。同时它也可以等价为操作一，即在 $p$ 和 $q$ 位值各执行一次操作一，这样的代价为 $2$。所以只有 $\lvert q-p \rvert \lt 2$ 时执行操作二是优的，其他情况一律执行操作一。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define random(a,b) (rand()%(b-a+1)+a)
#define se second
#define fi first
#define pr pair<int,int>
#define pb push_back
#define ph push
#define ft front
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Rep(i,a,b) for(int i=a;i>=b;i--)
#define mem(a,b) memset(a,b,sizeof a)
const int N=1e6+10;
int n,ans;
char a[N],b[N];
int main()
{
	ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>a+1>>b+1;
    For(i,1,n)
	{
		if(a[i]!=b[i]&&a[i+1]!=b[i+1]&&a[i]!=a[i+1])
		{
			i++;
			ans++;
		}
		else if(a[i]!=b[i]) ans++;
	} 
	cout<<ans;
	return 0;
}