Codeforce 1037C Equalize (贪心?)【2018.9.2混合场】No.12

Equalize

传送
You are given two binary strings a and b of the same length. You can performthe following two operations on the string a:
Swap any two bits at indices i and j respectively (1≤i,j≤n), the cost of this operation is |i−j|, that is, the absolute difference between i and j.
Select any arbitrary index i (1≤i≤n) and flip (change 0 to 1 or 1 to 0) the bit at this index. The cost of this operation is 1.
Find the minimum cost to make the string a equal to b. It is not allowed to modify string b.

Input

The first line contains a single integer n (1≤n≤106) — the length of the strings a and b.
The second and third lines contain strings a and b respectively.
Both strings a and b have length n and contain only ‘0’ and ‘1’.

Output

Output the minimum cost to make the string a equal to b.

Examples

input

3
100
001

output

2

input

4
0101
0011

output

1

####Note
In the first example, one of the optimal solutions is to flip index 1 and index 3, the string a changes in the following way: “100” → “000” →”001”. The cost is 1+1=2.
The other optimal solution is to swap bits and indices 1 and 3, the string a changes then “100” → “001”, the cost is also |1−3|=2.

In the second example, the optimal solution is to swap bits at indices 2 and 3, the string a changes as “0101” → “0011”. The cost is |2−3|=1.

---

题目大意：

给两个长度为n的0101010字符串二进制数
你可以进行两个操作：
1.把1变为0或把0变为1，消耗一点能量
2.交换1和0，消耗|i-j|的能量
问最少消耗多少能量，才能把第一个二进制数变成第二个二进制数

做法：

noip期间我好像做过类似的题还有这个题比B好像还简单啊喂！
贪心？？？
反正如果用2操作的话不是相邻的交换就不如直接1操作
所以遍历一遍所有需要改动的 1或0 看看周围有没有同样需要改动的 0或1
如果有，2操作交换，其余的，用1操作

代码：

#include<iostream>
#include<cstdio>
using namespace std;
int a[1000010],b[1000010],c[1000010];
int n,num,ans;
int read(){
	int res=0;char ch=0;
	while(!isdigit(ch)) ch=getchar();
	if(isdigit(ch)) res=ch-'0';
	return res;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		a[i]=read();
	}
	for(int i=1;i<=n;i++){
		b[i]=read();
		c[i]=(a[i]+b[i])%2;
		if(c[i]==1) num++;
	}
	for(int i=1;i<=n;i++){
		if(c[i]==1&&c[i+1]==1&&a[i]+a[i+1]==1){
			ans+=1;
			num-=2;
			i++;
		}
	}
	ans+=num;
	cout<<ans<<endl;
}