有序链表快速lower_bound [Codeforces 843B]

题目描述:给一个n个元素升序排列的链表,要求找到第一个>=x的元素值,n=50000,最多查询2000次

原理:链表中随机选取p(p 的范围大约是 [500, 1000])个位置,排序后做lower_bound,再从lower_bound-1开始向后查找直到>=x或到达lower_bound的位置

注意:如果lower_bound为第一个元素,则需要从头开始查找

题目:Codeforces 843B
代码:

#include <cstring>
#include <cstdio>
#include <ctime>
#include <cassert>
#include <algorithm>
using namespace std;

const int MAXRAND = 500;
const int MAXN = 50010;
inline int myrand() {
    return ((rand() << 16) | rand()) & 0x7fffffff;
}

int N, ST, X, Nr;
int A[MAXRAND+10], Ans;
bool vis[MAXN];

struct item {
    int id, v, nxt;
    inline bool operator<(item rhs) const {
        return v < rhs.v;
    }
} V[MAXRAND+10];

int main() {
    int i, v, n;
    srand(998244353 ^ time(0));

    scanf("%d%d%d", &N, &ST, &X);
    if(MAXRAND >= N) { //Zero!!!
        for(i=1;i<=N;i++) {
            printf("? %d\n", i); fflush(stdout);
            scanf("%d%d", &v, &n);
            
            assert(v != -1 || n != -1);
            A[i] = v;
        }

        A[N+1] = -1;
        
        sort(A+1, A+N+1);
        Ans = *lower_bound(A+1, A+N+1, X);
    }
    else {
        //Rand selection
        for(i=1;i<=MAXRAND;i++) {
            while(1) {
                v = (myrand() % N) + 1;
                if(vis[v]) continue;
                
                vis[v] = 1;
                break;
            }
            
            V[i].id = v;
            printf("? %d\n", v); fflush(stdout);
            
            scanf("%d%d", &v, &n);
            assert(v != -1 || n != -1);
            
            V[i].v = v; V[i].nxt = n;
        }
        
        //Set tail
        V[MAXRAND + 1] = {-1, -1, -1};
        
        //Lower bound
        sort(V+1, V+MAXRAND+1);
        
        item VX = {0, X, 0};
        i = lower_bound(V+1, V+MAXRAND+1, VX) - V;
        
        if(V[i].v == X) Ans = X;
        else {
            Ans = V[i].v;
            
            int tail;
            if(i == 1) {
                tail = V[i].id;
                i = ST;
            }
            else {
                tail = V[i].id;
                i = V[i - 1].nxt;
            }
            
            while(i != -1 && i != tail) {
                printf("? %d\n", i); fflush(stdout);
                scanf("%d%d", &v, &n);
                
                assert(v != -1 || n != -1);
                
                if(v >= X) { Ans = v; break; }
                i = n;
            }
        }
    }
    printf("! %d\n", Ans >= X ? Ans : -1);
    fflush(stdout);
}

暂无评论

发表评论

*