CF1698D Fixed Point Guessing

· · 题解

思路： 二分

要学会关注数据范围。只能问 15 次，而 2^{14} \leq 10^4 \leq 2^{15} ，所以第一个想到的就是二分。

注意到 n 是个奇数，所以考虑奇偶性。我们发现一个性质：当一个区间内 原本属于这个区间的数 的个数为奇数时，那个没交换的数必定在这个区间内。很简单就能证明，因为只能两两交换，每个数只能经历一次交换，总个数为奇数，那么必有一个是没有交换的。如果你还没有理解，可以举个例子，比如: 3 2 1 5…… 你看，前四个数中有 3 个是属于 1 \sim 4 这个区间内的，也就是原来的区间内的，所以答案必在这个区间内。

那么实现就很简单了，代码如下：

#include<bits/stdc++.h>
using namespace std;
int t,n,a,x;
int main() {
    cin>>t;
    while(t--) {
        cin>>n;
        int l=1,r=n;
        while(l<r) { 
            int mid=(l+r)>>1;
            cout<<"? "<<l<<" "<<mid<<endl;
            fflush(stdout);
            int cnt=0;
            for(int i=l;i<=mid;i++) {
                cin>>x;
                if(x>=l&&x<=mid)cnt++;
            } 
            if(cnt%2==1)r=mid;
            else l=mid+1;
        }
        cout<<"! "<<l<<endl;
        fflush(stdout);
    }
}