AIM Tech Round 4 (Div. 2) D. Interactive LowerBound 交互式，随机算法

AIM Tech Round 4 (Div. 2)

题意：原本有一个序列，只告诉你个数 n、最小数的下标 start、x 。要你通过最多2000次交互式询问得出序列中第一个比 x 在的数是多少。序列是递增的单链表形式。

tags：

先随机选取999个不同下标，找到这999个数中比 x 小的最大的那个数的位置。然后从这个数按单链表往后找。

分析原理：选取了999个下标，然后还有1000次的询问机会，那只要我们能找到 x 前面的1000个数中的一个即可。所以出错的概率 (1 - 999 / n)¹⁰⁰⁰ ≈ 1.7·10^- 9 。

随机数的选取：一开始直接用 srand(time(0); rand(); 不知道为什么挖了。。看了别人博客，下面两种是比较方便的。

1】 mt19937 myrand(time(0)); id = myrand()；

2】 srand(time(NULL)); random_shuffle(s, s+n); 即把有序的数组变成随机数组

#include<bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:102400000,102400000")
#define rep(i,a,b) for (int i=a; i<=b; ++i)
#define per(i,b,a) for (int i=b; i>=a; --i)
#define mes(a,b)  memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
#define MP make_pair
#define PB push_back
#define fi  first
#define se  second
typedef long long ll;
const int N = 50005;

mt19937 myrand(time(0));

int n, st, x;
int main()
{
    scanf("%d%d%d", &n, &st, &x);
    int xi=-1, nex;

    int mx=-1, id=st;
    st = 0;
    for(int i=1; i<=1000; ++i)
    {
        st = myrand()%n + 1;
        printf("? %d
", st);    fflush(stdout);
        scanf("%d%d", &xi, &nex);
        if(xi<x && xi>mx)  mx=xi, id=nex;
    }

    rep(i,1,999)
    {
        if(id==-1) break;
        printf("? %d
", id);    fflush(stdout);
        scanf("%d%d", &xi, &nex);
        if(xi>=x) return 0*printf("! %d
", xi);
        id = nex;
    }
    printf("! -1
");

    return 0;
}