备战蓝桥杯--贪心算法刷题整理5

翻硬币(贪心算法)

看了一下网上的题解，感觉挺强，网友的做题思想值得借鉴，这里分享一下网友的链接，同时再分享一下自己的解题方案 链接： 题目描述：

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

桌上放着排成一排的若干硬币。我们用 * 表示正面，用 o 表示反面（是小写字母，不是零）。

比如，可能情形是：oo*oooo

如果同时翻转左边的两个硬币，则变为：oooo***oooo

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

我们约定：把翻动相邻的两个硬币叫做一步操作，那么要求： 输入格式

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

一个整数，表示最小操作步数。 思路： 找两个字符串不相同的位置，记录下所有不相同的下标，一对一对的求其下标的差值，最后再累加即可(题目间接告诉我们，不同的位置的个数一定是偶数) 举个例子：

#include"iostream"
using namespace std;
int a[1010];
int main(){
          
   
	string s, c;
	cin >> s >> c;
	
	int k = 0;
	// 从第一个字符串的第一个字符开始，与第二个字符的每一个字符一次比较
	// 只要有不同的，记录下标，结束内层循环 
	for(int i = 0;i < s.size();i ++){
          
   
		for(int j = i;j < c.size();j ++){
          
   
			if(s[i] != c[j]){
          
   
				a[k++] = i;
			}
			break;
		}
	} 
	
	int sum = 0; // 记录结果， 最小操作步数 
	
	for(int i = k-1;i > 0;i --){
          
    //倒着一对一对的相减 
		sum += (a[i] - a[i-1]);
		if(i%2 != 0){
          
    // 这里的作用就是为了可以 一对一对的操作 
			i --;
		}
	}
	
	cout << sum;
	return 0;
}