Codeforces Round #503 (by SIS, Div. 2)-D. The hat-白红宇

Codeforces Round #503 (by SIS, Div. 2)-D. The hat

阅读量：4114 次

发布时间：2019-05-25

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

D. The hat

题意：有n个人围在一起形成一个圈，当x>=1&&x<n/2时，x与(x+ n/2)坐在对面，每个人手里有一张牌，每个牌上面有一个数字，相邻两个人手中的牌上面的数字大小相差为1（+1,-1），现在问你有没有一个手中的牌与他对面人手中的牌相同，如果有输出这个人的编号，如果没有输出-1.这是一个交互题，你可以通过？x来询问x位置上人手中的数字。

思路：我们构造一个函数g[x]=f[x]-f[x+n/2],f[x]代表x位置的人手中的数字大小，由题意可知，我们的目标就是寻找一个x，使得g[x]=0,我们可以知道g[x+n/2]=-g[x],由于相邻两个数字之间差值为1，所以g[x]-g[x+1]={2,0，-2}，我们可以使用二分来寻找答案，l=1,r=n/2,mid=(l+r)/2，观察g[mid]与g[1]数值符号的关系，来改变二分的区间的大小。

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               #include
                
                 using namespace std;const int maxn=100050;int f[maxn];int n;int Sc(int x){ if(x>n/2) x=x-n/2; printf("? %d\n",x); fflush(stdout); int l; scanf("%d",&l); printf("? %d\n",x+n/2); fflush(stdout); int r; scanf("%d",&r); return r-l;}int main(){ scanf("%d",&n); f[1]=Sc(1); if(f[1]==0) { printf("! %d\n",1); fflush(stdout); return 0; } int l=1,r=n/2; while(l<=r) { int mid=(l+r)/2; f[mid]=Sc(mid); if(f[mid]==0) { printf("! %d\n",mid); fflush(stdout); return 0; } if(f[1]<0) { if(f[mid]<0) l=mid+1; else r=mid-1; } else if(f[1]>0) { if(f[mid]<0) r=mid-1; else l=mid+1; } } printf("! %d\n",-1); fflush(stdout); return 0;}

转载地址：http://xbgsi.baihongyu.com/

你可能感兴趣的文章