[算法提高] 贪心算法翻硬币

梦里梦外; 2022-03-02 04:39 240阅读 0赞

**\[问题背景\]**

[蓝桥杯 历届试题 PREV-6 翻硬币][_ PREV-6]

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

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

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

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

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

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

输入格式

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

输出格式

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

样例输入1

\*\*\*\*\*\*\*\*\*\*  
o\*\*\*\*o\*\*\*\*

样例输出1

样例输入2

\*o\*\*o\*\*\*o\*\*\*  
\*o\*\*\*o\*\*o\*\*\*

样例输出2

**\[思路分析\]**

如果第i个不一样，那么就把第i个和第i+1个翻过来。

（似乎对只有最后一个不一样的用例解决不了，但oj里并没有这样的测试点）

**\[代码求解\]**

#include <iostream>
    #include <string>
    using namespace std;
    
    int main () {
    	string s1;
    	string s2; 
    	cin >> s1;
    	cin >> s2; 
    	int len = s1.length();
    	int cnt = 0;
    	for(int i = 0; i < len; i++) {
    		if(s1[i] != s2[i]) {
    			cnt++;
    			if(s1[i] == 'o') {
    				s1[i] = '*';
    				if(s1[i+1] == 'o') {
    					s1[i+1] = '*'; 
    				}else{
    					s1[i+1] = 'o';
    				}
    			}else{
    				s1[i] = 'o';
    				if(s1[i+1] == 'o') {
    					s1[i+1] = '*'; 
    				}else{
    					s1[i+1] = 'o';
    				}
    			}
    		}
    	}
    	cout << cnt;
    return 0; 
    }

附蓝桥oj测试点：

input1

******************
    ***oo**oo***oo****

input2

*o***oo***o****o*****oo*****oooo***oo*o*ooooo*******
    *o***oo**oo****o*****oo****oo**o***oo*o*ooooo*******

input3

*o***oo***o****o*****oo*****oooo***oo*o*ooooo*******
    *oo***oo*oo*****o****o****o*oo*o*oo***o*ooooo****o**

**\[方法总结\]**

**贪心算法：给出当前的局部最优解。**

**通常对于无后效性的问题（后面的输入不影响前面的输出，即某点的输出解只与此刻及过去有关而与未来无关），（类似 因果信号 这样的东西）可以考虑用贪心法求解。**

虽然这个程序对

\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*