DDOSvoid's Blog

CF 1486C2 Guessing the Greatest (hard version)

发表于 分类于
本文字数： 820 阅读时长 ≈ 1 分钟

题目描述

http://codeforces.com/contest/1486/problem/C2

Solution

我们考虑将次大值变成一个端点，然后二分另一个端点即可

总共需要 $O(\log n)$ 次，需要注意二分的时候有一点细节

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>
#include <cstdio>
using namespace std;

int n;

int ask(int l, int r) {
    int ans;
    cout << "? " << l << " " << r << endl;
    cin >> ans; return ans; 
} 

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n;
    int p = ask(1, n);
    if (p == 1 || ask(1, p) != p) {
        int l = p + 1, r = n, m; 
        while (l < r) {
            m = l + r >> 1;
            if (ask(p, m) == p) r = m;
            else l = m + 1; 
        }
        cout << "! " << l << endl; 
    }
    else {
        int l = 1, r = p - 1, m;
        while (l < r) {
            m = l + r + 1 >> 1;
            if (ask(m, p) == p) l = m;
            else r = m - 1; 
        }
        cout << "! " << l << endl; 
    }
    return 0;
}