算法
由于要求最小的操作次数,所以对于同一枚硬币,最多只操作一次(操作多了也没用,重复是无效的)。同时利用贪心的想法,字符串从前往后遍历,如果对应位置的硬币类型不同,则翻转当前位置以及后一个位置的硬币(正确性不会证明,但这样做确实对),此时得到的就是最小操作数。
C++ 代码
#include<bits/stdc++.h>
using namespace std;
string a,b;
int ans;
string change(string x,int u)
{
if(x[u]=='*') x[u]='o';
else x[u] = '*';
if(x[u+1]=='*') x[u+1]='o';
else x[u+1]='*';
return x;
}
int main()
{
cin>>a>>b;
int n = a.size();
for(int i=0;i<n;i++)
{
if(a[i]!=b[i])
{
a = change(a,i);
ans++;
}
}
cout<<ans;
return 0;
}