题目描述

咳咳咳咳，这题还没大佬来发题解 我来混一波，思路在下面会有，嘻嘻嘻嘻~~~~。

是这样的，题目的*我都用中文代替了，原因是因为两个星号被认为是加粗字体，所以说没有办法正常显示题目，换成中文也是不错滴0.0。

小明正在玩一个“翻硬币”的游戏。

桌上放着排成一排的若干硬币。我们用 * 表示正面，用 o 表示反面（是小写字母，不是零）。

比如，可能情形是：星星oo星星oooo

如果同时翻转左边的两个硬币，则变为：oooo星星星oooo

现在小明的问题是：如果已知了初始状态和要达到的目标状态，每次只能同时翻转相邻的两个硬币,那么对特定的局面，最少要翻动多少次呢？

我们约定：把翻动相邻的两个硬币叫做一步操作。

样例

**********
o****o****

输出

5

算法思路

我们可以这样思考这个题目，我们如何使翻硬币次数最少就能达到最高目的呢？
不妨假设我们随便翻，如果这样，我们每改变一个位置的硬币，都会影响周围两个硬币的状态，且只能影响其中一个（要么前面的，要么后面的），这样话我们即使使用暴力枚举完成也无法保证其次数最少，怎么办让它次数最少呢？

很简单，我们每翻一个硬币就把他的状态固定下来，类似于费解的开关的题目，每一层灯的状态只能被下一层所更改，且保证上一层等都是亮的，这个题目也是类似的思想，我每翻一个硬币，就保证前面的硬币和目标硬币状态一样的，这样的话次数就最少了.........

仔细思考上面的思路，并不难理解，想明白上面的大体思路我们再来看怎样去翻，假设第二个位置和第三个位置不同，我怎么去翻，我一定要去翻第三个硬币来去影响第二个硬币，也可以理解为如果当前判断的硬币状态与目标硬币状态不同，我就翻当前状态的硬币，和下一个硬币，为什么要这样呢，为啥第二个位置不同就不能翻第二个硬币和第一个硬币呢？我前面说了，一定要保证翻过的硬币状态就和目标状态相同，也就是说，我在判断第一个硬币状态的时候就已经将第一个硬币状态确定下来了，第二个硬币无论如何不能影响第一个硬币，即我们在翻任何一个与目标硬币不相同的硬币时，只能翻下一个硬币，而不能翻前面的硬币，这个思路应该还是不难理解的.....

，，，看代码吧

时间复杂度

O（a.length（））；
大约是这样吧，内层循环被if条件限制了，这个复杂度应该是最优的，即目标硬币和输入硬币完全相同。

C++ 代码

#include<bits/stdc++.h> //万能头文件，，，偷个懒 嘻嘻
using namespace std;
string a,b;
int ans;
int main(){
    cin>>a>>b;
    for(int i=0;i<a.length();i++){
        if(b[i]==a[i]){ //如果目标状态和输入状态相同，跳过即可
            continue;
        }
        else{
            for(int j=i;j<=i+1;j++){ //更新当前硬币状态和下一个硬币状态
                if(a[j]=='o') a[j]='*';
                else a[j]='o';
            }

            ans++; //答案+1
        }
    }
    cout<<ans<<endl;//华丽的输出0.0
    return 0;
}

吓得我赶紧去打卡，，，，，如有错误，请及时批评，新手题解，望支持~
谢谢>....<~