解题思路:
这个题可以暴力求解,但是细微观察一下,题目是有规律可循的:
(下面说说的翻转都是指依次翻转两个相邻的位置,同题目中的意思)
就用例子来说吧:
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分
44 人评分
C语言程序设计教程(第三版)课后习题8.5 (C语言代码)浏览:503 |
汽水瓶 (C语言代码)怎么答案错误?????浏览:792 |
C语言训练-尼科彻斯定理 (C语言代码)。。。内含证明定理浏览:2055 |
C语言程序设计教程(第三版)课后习题7.2 (Java代码)浏览:681 |
C语言程序设计教程(第三版)课后习题5.7 (C语言代码)浏览:912 |
【密码】 (C语言代码)浏览:333 |
【数组的距离】 (C语言代码)浏览:728 |
c primer plus 第十二章 12.1小节浏览:375 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:547 |
求组合数 (C语言代码)浏览:1151 |