自动搬运

查看原文

来自洛谷，原作者为

	zzzyyyyhhhhh omori will become sunny

搬运于2025-08-24 23:07:49，当前版本为作者最后更新于2025-01-04 19:49:14，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

怎么没题解呢，那就发一篇吧。

首先考虑有 3 个位置，标号为 $a,b,c$，两两询问得到 $x=\min\{a,b\},y=\min\{a,c\},z=\min\{b,c\}$。$x,y,z$ 三个值中一定有两个相等，且这个值是三数中最小的数。又因为所有值互不相等，所以可以确定最小值的位置（例如如果 $x=y$ 那么最小值位置在 $a$ 处）。

现在有前缀最大值 $a$ 和次大值 $b$ 和 $\min\{a,b\}$，每次新加入一个 $c$ 就可以通过两次询问确定一个值。

但是这样的构造操作次数是 $2\times n-1$ 的，无法通过。考虑丧失了哪些性质。对于某些 $c$ 不需要询问两次，如果询问得到的结果 $x$ 小于前缀次大值，那么三数中最小值是 $x$ 且位置在 $c$。

所以现在次数为 $O(n+\texttt{前缀次大值个数})$。序列前缀最大值个数期望是 $\ln n$，那么前缀次大值期望个数小于 $2\times \ln n$（期望 $\ln n$ 个数更新前缀最大值时次大值被更新，又期望 $\ln n$ 个数可能更新次大值），可以通过本题。

注意要打乱序列。

#include<bits/stdc++.h>
using namespace std;
const int N = 2000;
int n,a[N],ans[N];
inline int ask(int x,int y)
{
	int tmp;
	cout<<"? "<<x<<' '<<y<<endl;
	cin>>tmp;
	return tmp;
}
int x,y,xx,yy,zz;
bool t;
inline void work(int z)
{
	yy=ask(x,z);
	if(yy<xx)
	{
		ans[z]=yy;
		return;
	}
	zz=ask(y,z);
	if(xx==yy)
		ans[x]=xx,x=z,xx=zz;
	else if(yy==zz)
		ans[z]=yy;
	else//xx==zz
		ans[y]=xx,y=z,xx=yy;
}
mt19937 rd(time(0));
signed main()
{
	cin>>n;
	for(int i=1;i<=n;i++)a[i]=i;
	if(n==2)
	{
		int tmp=ask(1,2);
		ans[1]=ans[2]=tmp;
	}
	else
	{
		shuffle(a+1,a+1+n,rd);
		x=a[1],y=a[2];
		xx=ask(a[1],a[2]);
		for(int i=3;i<=n;i++)
			work(a[i]);
		int tmp=max({xx,yy,zz});
		ans[x]=ans[y]=tmp;
	}
	cout<<"! ";
	for(int i=1;i<=n;i++)cout<<ans[i]<<' ';
	cout<<endl;
}