题意:
桌子上放着一排硬币,用 *
表示正面,用 o
表示反面,每次只能翻转相邻的两个硬币,求出从现状态到目标状态最少操作数。
思路:
简单的模拟题,可以从最左侧开始遍历,找到第一个不满足目标状态的硬币,把它和后面的硬币一起翻转(因为前面是满足目标状态的,所以只能翻转后面的),这样一直翻转到末尾就是最少的答案数。
code:
#include <bits/stdc++.h>
using namespace std;
string s1, s2;
int res;
int main()
{
cin >> s1 >> s2;
int len = s1.length();
for (int i = 0; i < len; i ++ )
{
if (s1[i] != s2[i])
{
res ++ ;
if (s1[i] == '*') s1[i] = 'o';
else s1[i] = '*';
if (s1[i + 1] == '*') s1[i + 1] = 'o';
else s1[i + 1] = '*';
}
}
cout << res << endl;
return 0;
}