1300*C. Social Distance（贪心构造）

本文主要是介绍1300*C. Social Distance（贪心构造），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Problem - 1367C - Codeforces

 

解析： 

        统计出所有连续0序列，并且记录其左右两侧有没有1，然后对于四种情况分别判断即可。

#include<bits/stdc++.h>
using namespace std;
int t,n,k;
signed main(){scanf("%d",&t);while(t--){scanf("%d%d",&n,&k);string s;cin>>s;int f=0,l,r,res=0,p,q;for(int i=0;i<n;i++){if(i==0&&s[i]=='0'){f=1,l=0,p=0;continue;}if(s[i]=='0'){if(!f) f=1,l=i,p=1;}else{if(f){r=i,f=0,q=1;if(p){if(q){int tt=(r-l);if((tt%(k+1))>=k) res+=tt/(k+1);else res+=tt/(k+1)-1;}else res+=(r-l)/(k+1);}else{if(q) res+=(r-l)/(k+1);else res+=1+(r-l-1)/(k+1);}p=q=0;}}}if(f){r=s.size();if(p){if(q){int tt=(r-l);if((tt%(k+1))>=k) res+=tt/(k+1);else res+=tt/(k+1)-1;}else res+=(r-l)/(k+1);}else{if(q) res+=(r-l)/(k+1);else res+=1+(r-l-1)/(k+1);}}printf("%d\n",res);}return 0;
}

这篇关于1300*C. Social Distance（贪心构造）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---