原题链接：蓝桥杯历届试题-翻硬币
解题思路:
这个题可以暴力求解，但是细微观察一下，题目是有规律可循的：
（下面说说的翻转都是指依次翻转两个相邻的位置，同题目中的意思）
就用例子来说吧：
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| * | * | * | o | * | * | * | o | * | * |
| * | o | * | * | * | o | * | * | * | * |
（用表格更容易看对其效果）
对于这两个链：只需要翻转4次就可以使两个链相同（只看出的），那么规律就是每两个相邻的不同位置的下标之差的和就是所求的最小次数（注意我说的是每两个相邻的位置，也就是每一个不同的位置只能用一次）。对于上述两个链计算过程就是（橙色）3-1 = 2，（蓝色）7 - 5 = 2；那么结果就是2 + 2 = 4；
在比如：
| 0 | 1 | 2 | 3 | 4 | 5 |
| * | * | * | * | * | * |
| o | * | * | * | * | o |
这两个链需要翻转的最少次数为：5 - 0 = 5；即5次；
上面两个例子，大家应该都可以看出了吧；
或许有人想到了这个例子：
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| * | * | * | * | * | * | o | * | * | * |
| * | o | * | * | * | * | * | * | * | o |
对于这两个链上面的规律就“失效了”，但是大家仔细观察，这种情况应该是无解的，所以上面总结的规律是正确的。
注意事项:
注意的我的代码中，如何来算每相邻不同位置的差的总和的，也就是start的妙用。
参考代码:
#include <iostream>
#include <string>
using namespace std;
int main()
{
string str1, str2;
cin >> str1 >> str2;
int start = 0, cnt = 0;
for(int i = 0; i < str1.size(); ++i) {
if(str1[i] != str2[i]) {
if(start) {
cnt += (i - start);
start = 0;
} else {
start = i;
}
}
}
cout << cnt << endl;
return 0;
}0.0分
28 人评分
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：
一点编程也不会写的：零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码？手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
发表评论 取消回复