CF1486C Guessing the Greatest

题目链接:easy version

题目链接:hard version

题目描述

这是一道交互题

给你一个由 n不同数字构成的数组 a

在一次询问中,你可以提问子段 a[l\cdots r] 中第二个元素的位置。.你需要在不多于 40 次询问(easy version, hard vision为 20 次)后中找到整个数组 a 中最大元素的位置。

Solution

考场上把 easy vision 想出来了。。但可能就是因为无法跳出 easy version 的思路所以想不到 hard version。。

easy version

​ 考虑对 a[l…r] 询问,得到答案 x_0

​ 令 mid[l,r] 的中点。

​ 如果 x_0 \in [l,mid] ,那么考虑对 a[l\cdots mid] 询问,得到答案 x_l ,如果x_l=x ,那么整道题的答案x_a 必有 x_a\in [l,mid];如果 x_l \neq x ,那么 x_a\in [mid+1,r]

​ 同理,如果 x_0 \in [mid+1,r] ,那么考虑对 a[mid+1\cdots r] 询问,得到答案 x_r ,如果x_r=x ,那么整道题的答案x_a 必有 x_a\in [mid+1,r];如果 x_r \neq x ,那么 x_a\in [l,mid]

解释一下,我们假设为第一种情况。(第二种情况对称的)

​ 现在有 x_0 \in [l,mid] ,讨论两种子情况,一种是 x_a \in [l,mid],那么再对 a[l\cdots mid] 询问得到答案 x_l,这种情况必然有 x_0=x_l 。那么反过来,就可以得知 x_a \in [l,mid]。另一种是 x_a \in [mid+1,r] ,那这种情况就必然有 x_0\neq x_l ,那么可以反推出 x_a \in [mid+1,r]

​ 询问次数计算:每一次将区间缩小 \frac{1}{2} ,而每个区间最多询问两次,最少询问一次(对[l\cdots r],可能只用询问一半,也有可能两半都要询问)。所以询问次数为 log_2(n)*2 \leq 34

hard version

先对 [1\cdots,n] 询问,得到位置 x_0 ,然后尝试询问 [1\cdots x_0][x_0\cdots n] ,得到答案 x_lx_r

如果 x_l=x_0 那么可以知道最大值必然再 [1\cdots x_0] ,那么对这个区间进行二分,就可以确定 x_a 的位置。

询问次数为 log_2(n)+2 \leq 19

easy version

#include<bits/stdc++.h>
int n;
int get(int l,int r){
    if(l==r) return 0;
    printf("? %d %d\n",l,r);
    fflush(stdout);
    int x ;
    scanf("%d",&x);
    return x;
}
int ask(int l,int r,int x){
    if(l==r) return l;
    if(!x) x=get(l,r);
    int mid = l+r>>1;
    if(l<=x&&x<=mid){
        int L = get(l,mid);
        if(L==x) return ask(l,mid,L);
        return ask(mid+1,r,0);  
    }
    else{
        int R = get(mid+1,r);
        if(R==x) return ask(mid+1,r,R);
        return ask(l,mid,0);
    }
}
int main(){
    scanf("%d",&n);
    int ans = ask(1,n,0);
    printf("! %d",ans);
    fflush(stdout);
    return 0;
}

hard version

#include<bits/stdc++.h>
const int N = 1010;
int n;
int get(int l,int r){
    if(l==r) return 0;
    printf("? %d %d\n",l,r);
    fflush(stdout);
    int x;
    scanf("%d",&x);
    return x;
}
int L(int l,int x){
    int r=x;
    while(l+1<r){
        int mid = l + r >> 1;
        if(get(mid,x)==x) l=mid;
        else r=mid;
    }
    return l;
}
int R(int x,int r){
    int l=x;
    while(l+1<r){
        int mid = l + r >> 1;
        if(get(x,mid)==x) r=mid;
        else l=mid;
    }
    return r;
}
int main(){
    scanf("%d",&n);
    int x = get(1,n),ans;
    if(x==1) ans=R(1,n);
    else if(x==n) ans=L(1,n);
    else {
        int P = get(1,x);
        if(P==x) ans=L(1,x);
        else ans=R(x,n);
    }
    printf("! %d",ans);
    fflush(stdout);
    return 0;
}
分类: 二分答案

0 条评论

发表评论

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注