原题链接
题意：
交互题，首先电脑给出序列的长度n。你可以询问区间[l,r]的次大值位置，求序列最大值的位置。
思路：
首先考虑最简单的情况，当区间长度为2时，那么假设区间为[l,r]。当询问的次大值位置为l时，最大值位置就是r；当询问的次大值位置为r时，最大值位置就是l；
推广到任意长度区间，考虑二分。假设区间为[l,r]，中点为mid，区间[l,r]的次大值位置为pos。分别查询得到区间[l,mid]的次大值位置为tl,区间[mid,r]的次大值位置为tr。然后分类讨论：
如果说pos<=mid的话，那么区间[l,r]的次大值在区间[l,mid]之间，这时候如果说区间[l,mid]的次大值位置和pos相等的话，就说明最大值在[l,mid]之间。否则，就在[mid,r]之间。
递归下去就好了。
询问次数=2*log（1e5）
代码：
#pragma GCC optimize(2) #include<bits/stdc++.h> using namespace std; typedef long long ll;typedef unsigned long long ull; typedef pair<ll,ll>PLL;typedef pair<int,int>PII;typedef pair<double,double>PDD; #define I_int ll inline ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;} #define read read() #define closeSync ios::sync_with_stdio(0);cin.tie(0);cout.tie(0) #define multiCase int T;cin>>T;for(int t=1;t<=T;t++) #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i<(b);i++) #define per(i,a,b) for(int i=(a);i>=(b);i--) #define perr(i,a,b) for(int i=(a);i>(b);i--) ll ksm(ll a,ll b,ll p){ll res=1;while(b){if(b&1)res=res*a%p;a=a*a%p;b>>=1;}return res;} const int maxn=1e6+7; int n; int ask(int l,int r){ if(l>=r) return -1; cout<<"? "<<l<<" "<<r<<endl; fflush(stdout); int pos;cin>>pos; return pos; } int qask(int l,int r,int pos){ ///pos表示区间[l,r]次大值的位置 if(r-l==1){//区间长度为2时 if(pos==l) return r; else return l; } int mid=(l+r)/2; int tl=ask(l,mid),tr=ask(mid,r); if(pos<=mid){ if(tl==pos) return qask(l,mid,tl);///最大值在[l,mid]里 else return qask(mid,r,tr);///最大值在[mid,r]里 } else{ if(tr==pos) return qask(mid,r,tr);///最大值在[mid,r]里 else return qask(l,mid,tl);///最大值在[l,mid]里 } } void solve(){ n=read; cout<<"! "<<qask(1,n,ask(1,n))<<endl; } int main(){ int T=1; while(T--) solve(); return 0; }
