题解 | #翻硬币#

翻硬币

题意：输入两个表示硬币正反面状态的字符串，进行翻转操作使得初始状态达到目标状态，每次翻转只能同时操作相邻的两个硬币。

题解: 因为只能反转相同的连续的两个硬币，所有从前往后遍历，遇到不相同的就将当前位和后面一位反过来，后面一位不用管，因为下一次遍历就会到这个字符。遍历到字符串倒数第二位截止，因为如果要翻动倒数以一个，倒数第二个也被翻。当我们遍历完这个字符串的时候，只需要判断两个字符串的最后一位相不相同，相同则输出次数，不相同则No Answer.时间复杂度O(n).

#include<iostream>
#include<string>

using namespace std;

int main()
{

	string a, b;//a为初始状态，b为目标状态
	cin >> a >> b;

	int cnt = 0;//记录反转次数
	for (int i = 0; i < a.size()-1; i++)
	{
		if (a[i] != b[i])//不同就翻
		{
			a[i] = b[i];
			if (a[i + 1] == '*')a[i + 1] = 'o';//同时翻下一个
			else a[i + 1] = '*';
			cnt++;
		}
	}
    
	if (a[a.size()-1] != b[a.size()-1])//判断最后一位是否相等
        cout << "No Answer.";
	else cout << cnt;

	
	return 0;
}