蓝桥杯 2013 省B H题 翻硬币

翻硬币

题目背景

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



题目描述

桌上放着排成一排的若干硬币。我们用 * 表示正面，用 o 表示反面（是小写字母，不是零），比如可能情形是 **oo***oooo，如果同时翻转左边的两个硬币，则变为 oooo***oooo。



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



输入格式

两行等长字符串，分别表示初始状态和要达到的目标状态，每行长度小于 1000。



输出格式

一个整数，表示最小操作步数。



注意：数据保证一定存在至少一种方案可以从初始状态达到目标状态。



题解思路

由于翻转相邻两个硬币两次相当于不翻，因此在最优方案中，同一组相邻硬币最多只会翻转一次。翻转顺序不影响最终结果，故可以采用贪心策略：



从前往后比较初始状态与目标状态。

发现当前位置硬币不同时，立即翻转该硬币及其后方紧邻的硬币。

计数器累加。

遍历完成后，累加结果即为最少操作次数。

#include

using namespace std;



/**

* 翻转函数：切换两个硬币的状态

*/

void Switch(char &a, char &b) {

a = (a == '*' ? 'o' : '*');

b = (b == '*' ? 'o' : '*');

}



int main() {

string a, b;

if (!(cin >> a >> b)) return 0;



int cnt = 0;

// 修正：从 0 开始遍历到 size-2

for (int i = 0; i < (int)a.size() - 1; i++) {

if (a[i] != b[i]) {

Switch(a[i], a[i + 1]);

cnt++;

}

}



cout << cnt << "\n";

return 0;

}