题意： 给你一个序列，0表示空，1表示非空 你需要填k+1个位置，然后找出某一点到其他所有点都是最近的，然后输出一个最近的情况的最远点。 思路： 哎，好菜哦。。。不会写这个二分。。。 遍历每个可取的位置，以区间>=k+1为判断条件，然后二分整个区间，逐渐逼近这个距离。。。 好菜啊，代码借鉴某巨巨…也是吃到苦头了…要多写些了…
#include<iostream> #include<cstdio> #include<map> #include<set> #include<string> #include<queue> #include<math.h> #include<string.h> #include<algorithm> using namespace std; #define eps 1e-8 typedef __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; }