CF843B Interactive LowerBound

BADFIVE · 2021-07-12 20:54:17 · 题解

思路：把链表读入进来，随机询问 1000 次，找到最大的 <x 的数，并记录下来。
这 1000 个点是在链表中均匀分布的。就直接用一个部分暴力询问。

实际上，从整个序列里面随机选 1000 个数出来询问，然后从里面找出比 x 小的最大的那个，再往后面搜 1000 个数。所以直接用随机化就可以了。

因为已知该链表是递增的，可以先随机询问 \min(n,1000)-1 个点，记录好 \le x 的最大元素以及它的后面一项的地址。因为询问数 < n 的最大可能值，我们将这些询问近似地看做随机的。

参考代码：

#include<bits/stdc++.h>
using namespace std;
int n,a,x,ans;
int arr[100001],brr[100001];
int main(){
    srand(time(0));
    cin>>n>>a>>x;
    ans=a;
    for(int i=1;i<=1000;i++){
        int res=1ll*rand()*rand()%n+1;
        cout<<"? "<<res<<endl;
        cin>>arr[res]>>brr[res];
        if(arr[ans]<arr[res]&&arr[res]<=x){
            ans=res;
        }
    }
    for(int i=ans;i!=-1;i=brr[i]){
        cout<<"? "<<i<<endl;
        cin>>arr[i]>>brr[i];
        if(arr[i]>=x){
            cout<<"! "<<arr[i]<<endl;
            return 0;
        }
    }
    cout<<"! -1"<<endl;
}