专栏文章

题解：CF1486C1 Guessing the Greatest (easy version)

wwenmingge
CF1486C1题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mipy1w9v
此快照首次捕获于
2025/12/03 19:49
3 个月前
此快照最后确认于
2025/12/03 19:49
3 个月前
查看原文

思路

一个简单的分治。
对于长度为 11：明显直接输出即可。
对于长度为 22：问，看是左边的还是右边的，问来的答案的反方向就是答案。
否则：最开始问第二小，然后递归到第二小所在区间（只有第一在时它才可能是第二）。

代码

CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
int ask(int l,int r)
{
	cout<<"? "<<l<<" "<<r<<endl;
	int x;
	cin>>x;
	return x;
}
void ans(int x)
{
	cout<<"! "<<x<<endl;
	exit(0);
}
void find(int l, int r)
{
	if(l==r)ans(l);
	if(r-l==1)
	{
		if(l==ask(l,r))ans(r);
		else ans(l);
	}
	int maxid=ask(l,r),mid=(l+r)>>1;
	if(l<=maxid&&maxid<=mid)
	{
		if(ask(l,mid)==maxid)find(l,mid);
		else find(mid,r);
	}
	else
	{
		if(ask(mid,r)==maxid)find(mid,r);
		else find(l,mid);
	}
}
signed main()
{
	cin>>n;
	find(1,n);
	return 0;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...