Codeforces645C【二分】-白红宇

Codeforces645C【二分】

阅读量：5064 次

发布时间：2019-06-12

本文共 1134 字，大约阅读时间需要 3 分钟。

题意：

给你一个序列，0表示空，1表示非空

你需要填k+1个位置，然后找出某一点到其他所有点都是最近的，然后输出一个最近的情况的最远点。

思路：

哎，好菜哦。。。不会写这个二分。。。

遍历每个可取的位置，以区间>=k+1为判断条件，然后二分整个区间，逐渐逼近这个距离。。。

好菜啊，代码借鉴某巨巨…也是吃到苦头了…要多写些了…

#include
     
      #include
      
       #include
       #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              using namespace std;#define eps 1e-8typedef __int64 LL;/*以一个判断条件进行判断条件，即区间和>=k+1;*/const int N=1e5+10;const int INF=1e5+10;char s[N];int sum[N];int ans;int n,k;//其实最近的话，可想而知这个FJ在比较中间的bool Judge(int pos,int len){ int L=max(1,pos-len); int R=min(n,pos+len); return (sum[R]-sum[L-1])>=(k+1);}int solve(int pos){ int s=1,t=n; while(s<=t) { int mid=(s+t)/2; if(Judge(pos,mid))//以某个位置，满足区间和>=k+1,然后逐步逼近这个mid { ans=mid; t=mid-1; } else s=mid+1; } return ans;}int main(){ scanf("%d%d",&n,&k); scanf("%s",s+1); memset(sum,0,sizeof(sum)); for(int i=1;i<=n;i++) { if(s[i]=='0') sum[i]=sum[i-1]+1; else sum[i]=sum[i-1]; } int ans=INF; for(int i=1;i<=n;i++) { if(s[i]=='1') continue; ans=min(ans,solve(i)); } printf("%d\n",ans); return 0;}