Problem - C - Codeforces

题意：

一个01字符串a,b。选中一个a[i]==1不动，其他的a[i]进行翻转，具体是‘1’变成‘0’，‘0’变成‘1’

求最少次数由a变成b

感悟：

这个题思路挺清晰的，就是我代码的判断条件不太明确，导致错了几次，下次每种条件下想清楚了再写

分析：

如果自己创建一个随意的01串，然后随意的翻转几次，就可以发现：

假设a中的‘1’个数为cnt1，b中的‘1‘个数为cnt2

把a翻转一次，那a中的’1‘的个数会变成n-cnt1+1，如果再翻转一次会还原到cnt1

所以不管怎么翻转，a中’1‘的个数总是为cnt1或者n-cnt1+1，那么如果cnt2不等于这两个中的任何一个，那么答案就是-1。

上面是不合法的情况，那么合法的呢

因为翻转两次会还原到原来的个数，仔细发现，其实就是a中的某一个’1‘和某一个’0‘交换了位置，个数并没有发生任何改变。第一次翻转，一个’1‘不变，第二次翻转另外一个’1‘不变（但是是由原来的一个’0‘变成’1‘的，第一个不变的’1‘会在第二次翻转的时候变成’0‘）。所以只是a中原来的某一个’1‘和某一个’0’交换了位置而已。

一）cnt1==cnt2：可以看出交换了一次位置的代价是+2，交换位置本身个数不变。所以在cnt1==cnt2的时候会选择去交换位置，因为是两两搭配的原因，只需要交换（a[i]!=b[i]）个数/2，因为交换一次的代价是2，所以（a[i]!=b[i]）个数/2*2，所以这种情况的答案就是(a[i]!=b[i])的个数

二）cnt1！=cnt2：那就是cnt2==n-cnt1+1。那就要进行一次改变了，首先要翻转一遍：

翻转的时候又要分类讨论：

第一：有(a[i]==b[i]&&a[i]=='1')的情况，这样翻转之后的代价会少一个

第二：没有上述情况，那就翻转随意一个a[i]=='1'

上面翻转完之后cnt1就等于了cnt2，下面转回第一种情况

三）cnt1==cnt2&&cnt2==n-cnt1+1，这种情况也是有的，比如n==9，cnt1==5，cnt2==5。那这种情况就要取上面两种情况的最小值了，可能要提前写。

上面是三种情况，分类讨论情况清楚就可以了。

下面看代码，代码可能有点乱，QAQ

signed main(){IOS;int T;//T=1;cin>>T;while(T--){int n;cin>>n;string a,b;cin>>a>>b;int cnt1=0,cnt2=0;for(int i=0;i