蓝桥杯：翻硬币

翻硬币【贪心】

题目描述

小明正在玩一个"翻硬币"的游戏。
桌上放着排成一排的若干硬币。我们用 * 表示正面，用 o 表示反面（是小写字母，不是零）。
比如，可能情形是：* * o o* * * oooo;
如果同时翻转左边的两个硬币，则变为：oooo***oooo。
现在小明的问题是：如果已知了初始状态和要达到的目标状态，每次只能同时翻转相邻的两个硬币,那么对特定的局面，最少要翻动多少次呢？
我们约定：把翻动相邻的两个硬币叫做一步操作。

输入描述

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

输出描述

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

输入样例

**********
o****o****
1
2

输出样例

5
1

思路：

1、如果对应的第一个硬币状态不相同，不论对应的第二个硬币状态是否相同，都一定要翻转前两个硬币。
2、如果对应的第一个硬币状态相同，那么一定不会翻转第一个硬币，因此，当前面对应的硬币状态相同的时候，我们不必考虑，
只需要考虑第一个不同的硬币的位置，将其翻转即可，当翻转相同后，同样不必考虑。 所以我们只需要从第一个硬币开始比较对应的状态，
如果相同则跳过，如果不同则翻转本身和后面一个硬币，翻转后继续前一个步骤。这一定是步数最少的情况。
例如样例中：
原始：* * * * * * * * * *
结束：o * * * * o * * * *
第1个字符不同，翻转1、2个字符：o o * * * * * * * *
第2个字符不同，翻转2、3个字符：o * o * * * * * * *
第3个字符不同，翻转3、4个字符：o * * o * * * * * *
第4个字符不同，翻转4、5个字符：o * * * 0 * * * * *
第5个字符不同，翻转5、6个字符：o * * * * o * * * *
所以一共翻转5次

代码:

#include
#include
int main()
{
	int count=0;
	char s1[1100],s2[1100];
	scanf("%s",s1);
	scanf("%s",s2);
	for(int i=0;i<strlen(s1);i++)
	{	//遍历字符串 
		if(s1[i]!=s2[i])
		{   //如果s1和s2不同 
			s1[i]=s2[i];   //将当前遍历的字符翻转
			//将当前遍历的字符的下一个字符翻转 
			if(s1[i+1]=='*')  
				s1[i+1]='o';
			else
				s1[i+1]='*';
			count++;  //计算翻转次数 
		}
	}
	printf("%d",count);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24