CodeForces 567D One

CodeForces 567D One

  题意就是给你一个1*n的地图，然后地图上有k艘船，Bob有ti次操作，给你一个操作序列，表示对该位置轰炸，每次操作操作完,Alice都会说miss，然后问你最早能通过哪次操作得知Alice撒谎，如果ti次操作里没一个符合就输出-1.

  思路就是随着操作次数的增加，能推出Alice撒谎的几率越大，所以这是一个类似递增的序列。假设0表示推不出撒谎，1表示推的出撒谎，那么操作序列对应的就是我们的目标就是找到第一个1对应的操作次数。然后接着就是用二分，二分前用给ans赋值-1，要是二分的过程中，找不到一个符合的那么ans就为-1，要是找得到符合的ans=mid，最后二分结束的时候，如果能推出撒谎的话，ans记录的必定是第一个能推出撒谎的操作位置，因为up是更新为mid-1.这里的符合不符合指的是操作次数为mid时，1到n能放置的船的个数是否大于等于k，是的话就不符合，不是的话就符合

#include<bits/stdc++.h>
using namespace std;
int n,k,sz,ti;
int m[2*100000+10],vis[2*100000+10];
bool check(int mid)
{int tmp1=0,kk=0;memset(vis,0,sizeof(vis));for(int i=1;i<=mid;i++)vis[m[i]]=1;for(int i=1;i<=n;i++){if(!vis[i]){tmp1++;if(tmp1==sz){kk++;tmp1=0;i++;}}elsetmp1=0;}if(kk<k)return true;return false;}
int main()
{cin>>n>>k>>sz>>ti;for(int i=1;i<=ti;i++)cin>>m[i];int low,up,mid,ans=-1;low=1;up=ti;while(up-low>=0){mid=(low+up)>>1;if(check(mid)){ans=mid;up=mid-1;}elselow=mid+1;}cout<<ans<<endl;return 0;}