二分+交互

二分交互
题面



题意
你每一次输出一个数，电脑内部就会根据预先写的答案然后判断大小。如果你猜的数较大，那么电脑就输入<，相反则输入>。如果相同则输出=。
分析
对于这道交互题目，注意先写输出然后再写输入。
首先我们看到任何电脑给出的答案范围都是1~1e9且为整数，所以我们就想是不是可以直接枚举所有整数然后判断呢？但由于这题目数据很大，这样暴力枚举就会出现超时现象。（备注：一般1s的题目，处理1e6以下都是适当的 1e7还行 1e8就可能会爆。
这时，我们就想怎样高效地枚举答案呢？二分就是一个特别高效的方法（复杂度为以2为底 n的对数）
通过二分出所有可能的答案然后让电脑输入字符，如果输入>，表示你输出的数据太小，可以调整left（二分的左边界）。相反，则调整你的right（二分的右边界）。如果是=就直接退出。
AC代码

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

int main()
{
	int left=1 ,right=1e9,mid;
	char a;
      while(left<=right){
		mid=left+(right-left)/2;//这样写可以避免mid=(right+left)/2中right+left爆数据
	printf("Q %d\n",mid);
        cout.flush();
        cin >> a;
        if(a =='>') left=mid+1;//减少运行时间
         else if(a =='<')  right=mid-1;//Mid已经判别过了，所以可以减少时间
         else
	      break;
    }
    return 0;
}