题干前提:
保证一定有解,所以s1,s2一定不一样的硬币个数一定为偶数。
思路:
类似于贪心,若当前硬币与要求的面式不一样,则翻转当前硬币与其下一个硬币。
注意:
为提高代码简洁性,若
s1[i]!=s2[i]
则只需要改变s1[i+1]即可,不需要再改变s1[i]的值,(虽然确实s1[i])改变了,但无需在代码中体现出来
简略证明:
对每个不一样的硬币,尽可能只翻转一次,but可能会导致后面相同的硬币被迫翻转。
这时,我们依照这个思路继续翻转这个硬币。
换言之,从某种角度来讲我们在不断缩小硬币的范围,直到最后只剩两枚硬币。
#include <iostream>
using namespace std;
int main()
{
string s1,s2;
cin>>s1>>s2;
int cnt=0;//记录反转次数
for(int i=0;i<s1.size();i++)
if(s1[i]!=s2[i])
{ cnt++;
if(s1[i+1]=='*') s1[i+1]='o';
else s1[i+1]='*';
}
cout<<cnt;
return 0;
}