题解：CF1486C1 Guessing the Greatest (easy version)

wenmingge · 2025-03-11 22:03:46 · 题解

思路

一个简单的分治。

对于长度为 1：明显直接输出即可。

对于长度为 2：问，看是左边的还是右边的，问来的答案的反方向就是答案。

否则：最开始问第二小，然后递归到第二小所在区间（只有第一在时它才可能是第二）。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
int ask(int l,int r)
{
    cout<<"? "<<l<<" "<<r<<endl;
    int x;
    cin>>x;
    return x;
}
void ans(int x)
{
    cout<<"! "<<x<<endl;
    exit(0);
}
void find(int l, int r)
{
    if(l==r)ans(l);
    if(r-l==1)
    {
        if(l==ask(l,r))ans(r);
        else ans(l);
    }
    int maxid=ask(l,r),mid=(l+r)>>1;
    if(l<=maxid&&maxid<=mid)
    {
        if(ask(l,mid)==maxid)find(l,mid);
        else find(mid,r);
    }
    else
    {
        if(ask(mid,r)==maxid)find(mid,r);
        else find(l,mid);
    }
}
signed main()
{
    cin>>n;
    find(1,n);
    return 0;
}