Codeforces 1367C. Social Distance
原题链接
简单
作者:
flowerhy
,
2024-07-25 18:38:29
,
所有人可见
,
阅读 3
算法1
(贪心)
1.贪心思想
从左到右扫一遍字符串,必须保证前k个字符和后k个字符都不包含1,那么将0->1,ans++;
2.如何记录后k个字符中1的存储情况
开一个数组,从右到左遍历过程中记录最近的1出现的情况
如 :010001
r[]={2,2,6,6,6,6};
3.如何记录前k个字符中1的位置
用一个变量 loc 来记录从左到右扫描的过程中往前方向离我最近的1的位置
for(int i=1;i<=n;i++){
// 0变成1的情况:
// 前k个字符中没有1 —— i-loc>=k+1
// 后k个字符中也没有1 —— r[i]-i>=k+1
if(str[i]=='0'&&i-loc>=k+1&&r[i]-i>=k+1){
loc = i;
ans++; //0->1
}
//本身就是1的情况
if(str[i]==1) loc=i;
}
4.边界问题
1.当第1个数为0的情况 - loc设为无穷小
2.当第n个数为0的情况 - r[n+1] 设为无穷大
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
int T,n,k;
int idx,ans;
char str[N];
int r[N];
int main(){
cin>>T;
while(T--){
cin>>n>>k;
cin>>str+1;
//初始化
ans=0;
//处理边界情况
idx = -N*2;
r[n+1]=N*2;
//从右到左遍历一次-最近的 1
for(int i=n;i>=1;i--){
if(str[i]=='1'){
r[i]=i;
}
else r[i]=r[i+1];
}
//从左到右-前k个中有无1
for(int i=1;i<=n;i++){
if(str[i]=='0'&&i-idx>=k+1&&r[i]-i>=k+1){
idx=i; //当前位置0->1 往前最近的1出现的位置
ans++;
}
if(str[i]=='1') idx=i;
}
cout<<ans<<endl;
}
return 0;
}