01序列【牛客tracker 每日一题】
01序列
时间限制：1秒 空间限制：256M
知识点：模拟
网页链接
牛客tracker
牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！
题目描述
给定一个数组a r r a y arrayarray，数组中只包含1 11和0 00，且数组中的1 11都不相邻。
输入一个数n nn，问能否在将数组中n nn个0 00替代换成1 11后不破坏1 11都不相邻的条件。
- 例1a r r a y = [ 1 , 0 , 0 , 0 , 1 ] , n = 1 array=[1,0,0,0,1],n=1array=[1,0,0,0,1],n=1输出t r u e truetrue
- 例2a r r a y = [ 1 , 0 , 0 , 0 , 1 ] , n = 2 array=[1,0,0,0,1],n=2array=[1,0,0,0,1],n=2输出f a l s e falsefalse
输入描述：
输入一个数m ( 1 ≤ m ≤ 10 5 ) m(1≤m≤10^5)m(1≤m≤105)表示a r r a y arrayarray的长度
第二行m mm个数0 00或1 11表示该位置数组中的元素是0 00还是1 11
第三行输入一个数n nn
输出描述：
输出t r u e truetrue或f a l s e falsefalse
示例1
输入：
5 1 0 0 0 1 1输出：
true解题思路
本题核心是贪心遍历统计可替换为1的0的最大数量，判断其是否≥ ≥≥输入的n nn：首先遍历数组中的每个0 00，检查其左右相邻位置是否为1 11（若左/右是1 11则该0 00无法替换），若左右均非1 11则将该0 00标记为1 11（避免后续重复统计），并累加可替换的数量c n t cntcnt；遍历完成后，若n ≤ c n t n≤cntn≤cnt则输出t r u e truetrue，否则输出f a l s e falsefalse。该思路通过贪心策略优先标记可替换的0 00，确保统计的c n t cntcnt是数组能容纳的最大1 11的新增数量，时间复杂度为O ( m ) O(m)O(m)，适配m ≤ 1 e 5 m≤1e5m≤1e5的规模，精准判断是否能替换n nn个0 00为1 11且不破坏“1 11不相邻”的条件。
总结
- 核心逻辑：遍历数组，统计能替换为1 11且不与现有1 11相邻的0 00的最大数量c n t cntcnt。
- 关键判断：对每个0 00，检查左右是否为1 11，仅当均非1 11时标记为1 11并计数。
- 最终结论：比较n nn和c n t cntcnt，n ≤ c n t n≤cntn≤cnt则输出t r u e truetrue，否则输出f a l s e falsefalse。
代码内容
#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefpair<ll,ll>pii;constll N=1e5+10;constll p=1e9+7;chars[N];intmain(){ll m;cin>>m;for(ll i=0;i<m;i++)cin>>s[i];ll n;cin>>n;ll cnt=0;for(ll i=0;i<m;i++){if(s[i]=='0'){if(i-1>=0&&s[i-1]=='1')continue;if(i+1<n&&s[i+1]=='1')continue;s[i]='1';cnt++;}}if(n<=cnt)cout<<"true";elsecout<<"false";return0;}