cf 843 B Interactive LowerBound [随机化]

题面：

传送门

思路：

这是一道交互题

比赛的时候我看到了直接跳过了......

后来后面的题目卡住了就回来看这道题，发现其实比较水

实际上，从整个序列里面随机选1000个数出来询问，然后从里面找出比x小的最大的那个，再往后面搜1000个数（顺序），这样的方法，不成功率是1.7e-9......

所以随机化就可以了~

（要是这样还WA那真的是脸黑呢......）

Code：

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<ctime>

 using namespace std;

 int n,st,x;

 int val[],next[];

 int cnt;

 struct node{

     int v,p;

 }s[];

 bool cmp(node l,node r){

     return l.v<r.v;

 }

 int main(){

     int i,tmp,ttmp,t1,t2;

     srand(time(NULL));

     scanf("%d%d%d",&n,&st,&x);

     printf("? %d",st);

     scanf("%d%d",&t1,&t2);

     if(x<t1){

         printf("! -1");return ;

     }

     val[st]=t1;next[st]=t2;

     for(i=;i<=min(,n);i++){

         tmp=rand()*rand()%n+;

         printf("? %d",tmp);

         scanf("%d%d",&t1,&t2);

         s[++cnt].v=t1;s[cnt].p=tmp;

         val[tmp]=t1;next[tmp]=t2;

     }

     sort(s+,s+cnt+,cmp);

     for(i=;i<cnt;i++){

         if(s[i].v<x&&s[i+].v>=x) break;

     }

     tmp=s[i].p;

     if(n<=){

         printf("! %d",val[tmp]);return ;

     }

     for(i=;i<=;i++){

         ttmp=next[tmp];

         printf("? %d",ttmp);

         scanf("%d%d",&val[ttmp],&next[ttmp]);

         if(val[ttmp]>=x){

             printf("! %d",val[tmp]);return ;

         }

         tmp=ttmp;

     }

 }

巴特西

cf 843 B Interactive LowerBound [随机化]

最新文章

热门文章