Codeforce Round #700 Div 2 C题_codeforce fflush(stdout) or cout.flush() in c++;

这题是一道罕见的交互题。原题如下：

 大致题意是，给定一个由数字1-n的随机排列而成的数组，每个数字有且仅有出现一次的机会。初始只会给出n的值，然后你可以通过“? x”的形式来向电脑查询a[x]处的值，电脑会返回该值；

题目要求的是，求出数组中任意一个local minimum的下标位置。什么是local minimum呢？题目要求就是一个数比它两侧的数都要严格小于，也就是假设i是一个local minimum的下标，那么就必须满足a[i]<a[i-1]&&a[i]<a[i+1]；

题目限制“? x"的查询最多发生一百次，超过一百次会直接wa，也就是要求我们在至多一百次查询里找到一个local minimum的值。

刚拿到题目的时候是非常懵逼的，心里在不断纠结考虑100次查询，1e5的数据要怎么找，万一你连续查一百个，结果好巧不巧查的是一个单调递增或递减的片段那不是就寄了（）

然后我们可以看到题目里给出了两个非常重要的条件：在这个数组排列之外，a[0]=a[n+1]=+∞；

也就是说，a[1]必定小于a[0]，a[n]也必定小于a[n+1]；这意味着，对于边界上的这两个点，如果a[1]小于a[2]，亦或者a[n]小于a[n-1]，我们就直接得到了一个local minimum的值，本题就终结了。所以很自然的，我们开头先查询一下a[1],a[2],a[n-1],a[n]的值，看看能不能直接找到再说，找到了的话就不需要后续查询了（这里注意要处理n比较小的情况？有可能会造成重复查询同一个值，所以在代码中对一个位置进行查询赋值之前先判断了一下该位置是否有值）

那如果查不到呢？那就是告诉我们，a[1]>=a[2]&&a[n-1]<=a[n]；又因为该数组是1-n不重复的排列，故不存在取等于号的情况。

所谓local minimum，他在这个点处必然是呈现一个局部的“V”形图像，该点左侧必然是单调递减，这个点右侧则是单调递增。

那我们现在看这个数组：a[1]>a[2],函数图像在这时是单调递减的，而a[n-1]<a[n]，函数图像到这里又是单调递增的。这也就是说，这个数组在中间的至少必定存在一个位置，在这个位置使得这个函数图像的单调性发生了变化，从单调递减变成了单调递增，那么毫无疑问这个位置也就是我们要找的local minimum的下标位置。

我们要找到的就是这样一个拐点，然后就自然而然地轮到二分查找派上用场了。

对于每个二分的区间，查询其mid，mid-1，mid+1三个位置的值，判断拐点是否在此处，若拐点就在mid处则终止程序并输出，若拐点不在此处，则判断a[mid]和a[mid-1]的大小关系：a[mid]>a[mid-1]的话，说明函数图像在这里就已经是递增趋势了，那根据我们之前看到的，函数图像最开始是递减的，那么至少存在的那一个拐点就必然在mid点的左侧，二分的右边界就收缩到mid；反之，若a[mid]>a[mid+1]的话，那么我们就要去mid的右侧寻找拐点，把左边界收缩到mid+1；

我们每次查询三个值，mid，mid-1，mid+1，去掉最开始查询的四个值，我们还剩96次查询机会；每次至多查询三个值，96/3=32次机会；而1e5的二分查找自然是log2 1e5，结果大约在16-17之间，可以看到是能够符合题目要求的。

本题还有需要注意的坑就是交互题的交互方式。一个是清空输出缓存区的方式，即

• fflush(stdout) or cout.flush() in C++;
• System.out.flush() in Java;
• flush(output) in Pascal;
• stdout.flush() in Python;
• see documentation for other languages.

还有一个是输出“? x”中间的空格没打上直接idle limited exceeded好几次= =

再者就是二分查找的边界问题吧，l和r如何更新，要不要取等于，也是容易wa的点。

差不多了，下面附上代码：

#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=1e5+10;
int a[maxn];
int q(int x){
	cout<<"? "<<x<<endl;
	int n;cin>>n;
	fflush(stdout);
	return n;
}
int main(){
	int n;cin>>n;
	int l=1,r=n;
	if(n==1) {
		cout<<"! "<<1;return 0;
	}
	a[0]=maxn;a[n+1]=maxn;
	a[1]=q(1);a[n]=q(n);
	if(!a[2])a[2]=q(2);
	if(!a[n-1])a[n-1]=q(n-1);
	if(a[1]<a[2]) {
		cout<<"! "<<1;return 0;
	}
	if(a[n]<a[n-1]){
		cout<<"! "<<n;return 0;
	}
	while(l<r){
		int mid=l+r >>1;
		if(!a[mid-1])a[mid-1]=q(mid-1);
		if(!a[mid+1])a[mid+1]=q(mid+1);
		if(!a[mid])a[mid]=q(mid);
		if(a[mid]<a[mid-1]&&a[mid]<a[mid+1]) {
			cout<<"! "<<mid;return 0;
		}
		else{
			if(a[mid]>a[mid-1]){
				r=mid;
			}
			else l=mid+1;
		}
	}//���a[1]>a[2]<a[3] l=1 r=3 mid=2 l=3 r=4 mid=3  
	return 0;
}