Fixed Point Guessing（二分）

Problem - 1698D - Codeforces

Fixed Point Guessing - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include 
#include 
#include
#define x first
#define y second
#define  ios ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);using namespace std;typedef  long  long LL ;
typedef  unsigned long  long ULL ;
typedef pair PII ;
typedef pair PLI ;
const int N = 1e4 + 10 ,M=1000 + 10;
const LL INF2 = 1e17;// 对于 一个区间来说 两个数交换
// 要么是 这个区间里的一个数 和 外面区间的 一个数交换，进来一个数出去一个数，使得一个数 出去这个区间
// 要么是 这个区间的 内部进行交换 ，成对留在 这个区间int n;
inline void solve()
{cin >> n;int l=1,r=n;// 因为n为 奇数// 如果 下标[l,mid] 的数都被 交换过，那么在这个区间里 值为[l,mid]的 数的个数 为偶数个0~2*x//0: 全部与 区间外的数交换，2：有一对交换的 数在区间内 。。。// 如果 值在 这段区间的 个数为奇数，那么那个剩余的数 可以与区间外的数交换 来让这个数的值不在这个区间，// 但是这个数却留在了这个区间，说明这个数 就是我们要的 那个数 while(l < r ){int mid = (l + r ) /2 ;cout<<"? "<> x;if(x >= l && x <= mid ) cnt++ ;//当前读入的 这个 数在这个区间}// 考虑 极端情况 如果 这一段区间的数if(cnt & 1 ) r =mid; // 要找的数 在 左区间else l =mid + 1;}cout << "! " << l <>T;while(T -- ){solve();}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！