[蓝桥杯][历届试题]翻硬币 Easy only once *贪心问题

基本思想:

贪心思想掌握的还不是很好,在枚举情况漏了一种:

010

111

此时需要翻两次;

 

如果使用贪心策略,则是先寻找当下最优解,即:直接遇到不一样的直接翻,之后进行后续的判断;

 

关键点:

无;

 

#include<iostream>
#include<stdlib.h>
#include<stdio.h>
#include<vector> 
#include<string>
#include<math.h>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<set>
#include<stack>
using namespace std;


int main() {
    string s1, s2;
    cin >> s1 >> s2;
    int cnt = 0;
    for (int i = 0; i < s1.size(); i++) {
        if (s1[i] != s2[i]) {
            //当遇到不相等时;
            if (s1[i + 1] == '*')
                s1[i + 1] = 'o';
            else
                s1[i + 1] = '*';
            cnt++;
        }
    }
    cout << cnt;
    return 0;
}

 

上一篇:[蓝桥杯][算法提高VIP]排队打水问题 Easy only once *贪心算法


下一篇:cow and treats