Codeforces Round #700 (Div. 2) C. Searching Local Minimum（交互）_round 700

链接： C. Searching Local Minimum
题意： 给你一个大小为 n 排列 , 一次询问可以得到位置 i 的数，要求在不超过 100 次询问的条件下找到该排列的一个波谷，即找到位置 k满足：a[k] < a[k - 1] && a[k] < a[k + 1]。
思路：

1. 我们先假设 a[1]小于 a[n] , 因为已经保证了 a[0] 为 无穷大，所以可以保证 a[0] 已经大于 a[1] , 对于 1 到 n 这一部分，如果他保持单调递增或者 是 先增后减 那么答案就是 1 如果保持单调递减那么答案就是 n. 如果是先减后增那么答案就是那个波谷，所以我们可以证明 答案一定是存在的（当然如果 a[1] 大于 a[n]，那么答案同理也是存在的）。
2. 所以我们可以利用以上性质，假设存在一个区间 【l , r】，a[l] < a[r],并且 a[l-1] > a[l].那么在 l 到 r 内一定有解，所以我们只需要一直维护这样一个区间 ，并且通过二分不断缩小区间。那么最后一定能得到解。
3. 最后考虑怎么一直维持一个这样的区间 ， 让 mid = (l + r）/ 2,如过 a[l] < a[mid] ，那么就可以让 r = mid, 此时这个区间[l + 1,mid]仍满足上述条件。如果 a[l] > a[mid] ,那么我们考虑 mid - 1,如果 a[mid - 1] > a[mid],那么 [mid , r] 满足条件。否则的话我们就必须反向考虑 [l , mid - 1] ,也是满足的（注意这里是反向找，就相当于 一 开始 a[1] > a[n]) 具体可以看代码理解（用了flag表示方向）。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=4e6 + 7;
const int mod = 1e9 + 7;
int T;
int n,a[maxn],vis[maxn];
void query(int x){
     if(vis[x]) return ;
     printf ("? %d\n",x);
     fflush(stdout);
     scanf("%d",&a[x]);
     vis[x] = 1;
}
int main (){
    int l,r,mid;
    a[0] = a[n + 1] = n + 1;
    scanf("%d",&n);
    if(n == 1){
        printf ("! 1\n");
        return 0;
    }
    query(1);
    query(n);
    int flag = 1;
    if(a[1] > a[n]) flag = 0;
    l = 1,r = n;
    while(l <= r){
        if(flag){
            query(l + 1);
            if(a[l] < a[l + 1]){
                printf ("! %d\n",l);
                return 0;
            }
            mid = (l + r) / 2;
            query(mid);
            if(a[mid] > a[l]){
                r = mid;
                l += 1;
            }
            else{
                query(mid - 1);
                if(a[mid - 1] > a[mid]){
                    l = mid;
                }
                else {
                    r = mid - 1;
                    flag = 1 - flag;
                }
            }
        }
        else{
            query(r - 1);
            if(a[r] < a[r - 1]){
                printf ("! %d\n",r);
                return 0;
            }
            mid = (l + r) / 2;
            query(mid);
            if(a[mid] > a[r]){
                l = mid;
                r -= 1;
            }
            else{
                query(mid + 1);
                if(a[mid + 1] > a[mid]){
                    r = mid;
                }
                else {
                    l = mid + 1;
                    flag = 1 - flag;
                }
            }
        }
    }
    return 0;
}

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79