C2. Guessing the Greatest (hard version) 二分 交互题

C2. Guessing the Greatest (hard version) 二分 交互题

题目大意：

给你一个大小为 n 的序列，保证这 n 个数互不相同，每次询问一个区间 ([l,r] \,\,l<=r) ，返回这个区间的次大值的位置，要求你在 20 次询问内求出 ([1,n]) 的最大值。

题解：

一开始想岔了，直接说说正确思路吧。

• 首先求一个 ([1,n]) 的区间次大值的位置 (p)，然后判断一下最大值在哪个区间 ([1,p]) 还是 ([p,n])
• 求出之后，直接二分最大值的位置即可，以区间 ([1,p]) 为例，如果 ([x,p]) 的次大值 等于 (p) ，那么就说明最大值在区间 (x) 到 (p) ，如果不等于 (p) 说明最大值不在区间 ([x,p])

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int ask(int l,int r){
    printf("? %d %d
",l,r);
    fflush(stdout);
    int ans;
    scanf("%d",&ans);
    return ans;
}

int main(){
    int n;
    scanf("%d",&n);
    int p = ask(1,n);
    if(p>1&&ask(1,p)==p){
        int l = 1,r = p;
        while(r-l>1){
            int mid = (l+r)>>1;
            if(ask(mid,p)==p) l = mid;
            else r = mid;
        }
        printf("! %d
",l);
    }
    else {
        int l = p,r = n;
        while(r-l>1) {
            int mid = (l + r) >> 1;
            if (ask(p,mid) == p) r = mid;
            else l = mid;
        }
        printf("! %d
",r);
    }
    return 0;
}