蓝桥杯历届真题填充#贪心算法

2025/3/31 20:48:34 来源：https://blog.csdn.net/mzh1213/article/details/146485049 浏览: 次关键词：蓝桥杯历届真题填充#贪心算法

文章目录

题目解读
思路
- AC CODE
参考
注意

题目链接

题目解读

题目描述
有一个长度为 n 的 01 串，其中有一些位置标记为 ?，这些位置上可以任意填充 0 或者 1，请问如何填充这些位置使得这个 01 串中出现互不重叠的 00 和 11 子串最多，输出子串个数。
输入格式
输入一行包含一个字符串。
输出格式
输出一行包含一个整数表示答案。
样例输入
1110?0
样例输出
2
提示
如果在问号处填 0 ，则最多出现一个 00 和一个 11：111000 。

对于所有评测用例，1 ≤ n ≤ 1000000 。

思路

看到最大最小可以考虑一手贪心算法,然后直接猜出来一个规律。
然后去找一个反例证明其是错的,如果证明不出来,那么它就是对的!

贪心思路 : 从头往后枚举,如果能发生"配对"那么答案加1
配对儿 : 如果当前字符和下一个字符一致,或者两个连续的字符里出现一个问号,那么也可以配对儿成功。

AC CODE

#include<bits/stdc++.h>using namespace std;int main(){string s;cin >> s;int res=0;for(int i=0; i<s.size()-1; i++){char a=s[i];char b=s[i+1];if(a==b || a=='?' || b=='?'){res++;i++;	}} cout << res;return 0;
}