题解：CF1486C2 Guessing the Greatest (hard version)

题解：CF1486C2 Guessing the Greatest (hard version)

题意简述

有一个值均不同的数组，每次你可以询问一个子段次大值的位置，请你在 20 次询问之内找到最大值的位置。

解题思路

首先，我们确定全局次大值的位置，询问 (1 , n)，记为 q。

• 若 q = 1，则答案区间为 (2 , n)。
• 若 q = n，则答案区间为 (1 , n - 1)。
• 若 1 < q < n 且询问 (1 , q) = q，则答案区间为 (1 , q - 1)。
• 若 1 < q < n 且询问 (1 , q) \ne q，则答案区间为 (q + 1 , n)。

此时我们在答案区间中二分，为避免区间只有一个数的情况：

• 若 \frac{l + r}{2} < q，则 mid \gets \frac{l + r}{2} + 1。
• 若 \frac{l + r}{2} > q，则 mid \gets \frac{l + r}{2}。
• 可以证明不存在 \frac{l + r}{2} = q 的情况。

如果询问 (\min(mid , q) , \max(mid , q)) = q，那么最大值就在这个区间，反之不在。

参考代码

因为四种情况打了四个不太相同的二分，所以马蜂有点史，请见谅。

#include <bits/stdc++.h>
using namespace std;
int n , l , r , mid , ans , sec;
inline bool ask(int q)
{
    int x;
    cout << "? " << min(sec , q) << ' ' << max(sec , q) << endl;
    cin >> x;
    return x == sec;
}
int main()
{
    cin >> n;
    cout << "? 1 " << n << endl;
    cin >> sec;
    if(sec == 1)
    {
        l = 2;
        r = n;
        while(l <= r)
        {
            if(l == r)
            {
                ans = l;
                l++;
                continue;
            }
            mid = (l + r) / 2;
            if(mid == r)
            {
                mid--;
            }
            if(ask(mid))
            {
                ans = mid;
                r = mid;
            }
            else
            {
                l = mid + 1;
            }
        }
    }
    else if(sec == n)
    {
        l = 1;
        r = n - 1;
        while(l <= r)
        {
            if(l == r)
            {
                ans = l;
                l++;
                continue;
            }
            mid = (l + r + 1) / 2;
            if(mid == l)
            {
                mid++;
            }
            if(ask(mid))
            {
                ans = mid;
                l = mid;
            }
            else
            {
                r = mid - 1;
            }
        }
    }
    else
    {
        cout << "? 1 " << sec << endl;
        cin >> ans;
        if(ans == sec)
        {
            l = 1;
            r = sec - 1;
            while(l <= r)
            {
                if(l == r)
                {
                    ans = l;
                    l++;
                    continue;
                }
                mid = (l + r + 1) / 2;
                if(mid == l)
                {
                    mid++;
                }
                if(ask(mid))
                {
                    ans = mid;
                    l = mid;
                }
                else
                {
                    r = mid - 1;
                }
            }
        }
        else
        {
            l = sec + 1;
            r = n;
            while(l <= r)
            {
                if(l == r)
                {
                    ans = l;
                    l++;
                    continue;
                }
                mid = (l + r) / 2;
                if(mid == r)
                {
                    mid--;
                }
                if(ask(mid))
                {
                    ans = mid;
                    r = mid;
                }
                else
                {
                    l = mid + 1;
                }
            }
        }
    }
    cout << "! " << ans;
    return 0;
}

双倍经验：CF1486C1。