Codeforces Round #700 (Div. 2) C. Searching Local Minimum

题意：

交互题

有一个对你隐藏的长度为n的整数数组v（数组里面的数是1...n，且每一个数只能出现一次）。刚开始数组中每一个位置的值你都不知道，每一次你可以询问数组中某个位置的数是多少，你最多可以询问100次。最后你需要输出一个下标k，你需要保证v[k]<min(v[k-1],v[k+1])，题目设定v[0]=v[n+1]=无穷大

题解：

我们一直维护下面的状态

V_L<V_L-1  &&  V_R<V_R+1

这样子的话当L==R的时候就满足题目要我们找寻的k了

对于一个序列来说，满足题意的k的数量要么等于0，要么大于等于2

1，2，3，4，5，6，7，8这个序列满足题意的k的数量是0

1，7，3，4，5，6，2，8这个序列满足题意的k的数量为3，分别是k=1，3，7

这个性质就可以让我们去对V数组进行二分，因为这个性质表示满足题意的下标是有对称性质的（也不算对称，就是这样子的下标不会仅仅存在在数组一半的区域）

代码：

#include <stdio.h>
#include <iostream>
#include <string.h>
#include<vector>
#include<set>
#include<map>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn=1e5+10;
int n,v[maxn];
void get(int x)
{
    if( x>n||x<1||v[x] )    return;
    cout << "? " << x << endl;
    fflush(stdout);
    cin >> v[x];     
}
int main()
{
    scanf("%d",&n);
    v[0]=v[n+1]=1e9;
    get(1);
    get(n);
    int l=1,r=n;
    while(l<r){
        int mid=(l+r)>>1;
        get(mid),get(mid+1);
        if(v[mid]>v[mid+1]){
            l=mid+1;
        }else r=mid;
    }
    printf("! %d
",l);
    return 0;
}