咖啡


私信TA

用户名:Tianxn

访问量:127517

签 名:

十年OI一场空,不开LL见祖宗。

等  级
排  名 8
经  验 25962
参赛次数 10
文章发表 197
年  龄 22
在职情况 学生
学  校 西安电子科技大学
专  业 软件工程

  自我简介:

解题思路:

这个题可以暴力求解,但是细微观察一下,题目是有规律可循的:

(下面说说的翻转都是指依次翻转两个相邻的位置,同题目中的意思)

    就用例子来说吧:

0123456789
***o***o**
*o***o****

(用表格更容易看对其效果)

对于这两个链:只需要翻转4次就可以使两个链相同(只看出的),那么规律就是每两个相邻的不同位置的下标之差的和就是所求的最小次数(注意我说的是每两个相邻的位置,也就是每一个不同的位置只能用一次)。对于上述两个链计算过程就是(橙色)3-1 = 2,(蓝色)7 - 5 = 2;那么结果就是2 + 2 = 4;


在比如:

012345
******
o****o

这两个链需要翻转的最少次数为:5 - 0 = 5;即5次;


上面两个例子,大家应该都可以看出了吧;


或许有人想到了这个例子:

0123456789
******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 人评分

  评论区

start初始化为-1就可以了,if(start!=-1)
2022-02-05 14:37:45
*o*o*o
o*oo**
这个过不了  要4次不是1次
2021-11-26 09:28:55
nice
2021-10-07 14:14:55
*o*o*o
o*oo**
老哥这个应该过不了
数组下标从0开始要是第一个就不同start=i,i没变还是0;
2020-05-24 22:12:26
怎么发现这个规律的?
2020-01-24 19:50:41
nice
2019-11-14 15:09:18
感觉这个规律不是很好发现,怎么发现这个规律的?
2019-11-10 18:26:37
66666
2019-06-09 08:54:42
  • «
  • 1
  • »