D. Fixed Point Guessing(二分+交互式问题)

Problem - D - Codeforces

 

这是一个互动问题。

最初，有一个数组a=[1,2,...,n]，其中n是一个奇数正整数。陪审团选择了n-12对不相干的元素，然后对这些元素进行交换。例如，如果a=[1,2,3,4,5]，对1↔4和3↔5进行互换，那么得到的数组是[4,2,5,1,3]。

由于这些交换的结果，正好有一个元素不会改变位置。你需要找到这个元素。

要做到这一点，你可以提出几个查询。在每个查询中，你可以选择两个整数l和r（1≤l≤r≤n）。作为回报，你将得到子数组[al,al+1,...,ar]中按递增顺序排列的元素。

找到没有改变位置的元素。你最多可以进行15次查询。

数组a在交互之前是固定的，在你的查询之后没有变化。

回顾一下，如果一个数组b可以从a中删除几个（可能是零个或全部）元素和几个（可能是零个或全部）元素，那么这个数组就是a的子数组。

输入
每个测试包含多个测试案例。第一行包含一个整数t（1≤t≤500）--测试案例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数n（3≤n<104；n是奇数）--数组a的长度。

在读完每个测试案例的第一行后，你应该开始互动。

保证所有测试用例的n之和不超过104。

题解:
根据题目说不超过15次查询,我们可以分析出需要二分,我们二分应该二分其区间,

那我们如何check呢

不妨设cnt为得到的x在l~r区间的数目

如果x在l~r区间有两种情况

1.他就是我们要找的位置不变的数

2.它交换了，但是它仍在区间内，所以它是与区间内的另一个元素交换的

所以如果val为奇数说明答案在这个区间里,否则说明在另一个区间里

#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<map>
#include<vector>
#include<queue>
using namespace std;
#define int long long
//1 1 3 3 3
int n;
int check(int l,int r)
{
	cout<<"? "<<l<<" "<<r<<"\n";
	int cnt = 0;
	for(int i = l;i <= r;i++)
	{
		int x;
		cin >> x;
		if(x >= l&&x <=r)
		{
			cnt++;
		}
	} 
	return cnt%2 == 1;
}
void solve()
{
	cin >> n;
	int l = 1,r = n;
	int ans = 0;
	while(l <= r)
	{
		int mid = (l+r)/2;
		if(check(l,mid))
		{
			ans = mid;
			r = mid - 1;
		}
		else
		{
			l = mid + 1;
		} 
	}
	cout<<"! "<<ans<<"\n";
}
signed main()
{
	int t = 1;
	cin >> t;
	while(t--)
	{
		solve();
	}
}
//2 5
//3
//9 7 
 
 
//2  3 4 3
//1 2 3 4 5
//      3