交互题。有一个 $1\sim n$ 的排列 $\{p_n\}$ ,每次可以询问 $(x,y)$ ,得知 $p_x\bmod p_y$ 。在 $2n$ 次询问内问出这个排列。
考虑两个数 $A,B(A\not=B)$ 之间取模:
因此两个不相等数之间只需要问两次就可以得知小的那一个。
所以只需要每次挑出两个还没确定的位置就可以问出其中一个了,总共需要问 $2(n-1)$ 次。
用并查集快速查找还没确定的位置,用链表也行。
#include<cstdio>
using namespace std;
const int maxn=10000;
int n,a[maxn+5],fat[maxn+5];bool vis[maxn+5];
void Ask(int x,int y) {printf("? %d %d\n",x,y);fflush(stdout);}
int getfa(int x) {return x==fat[x]?x:fat[x]=getfa(fat[x]);}
int main(){
scanf("%d",&n);
for (int i=1;i<=n+1;i++) fat[i]=i;
for (int t=1;t<n;t++){
int i=getfa(1),j=getfa(i+1);
int A;Ask(i,j);scanf("%d",&A);
int B;Ask(j,i);scanf("%d",&B);
if (A<B) a[j]=B,vis[B]=true,fat[j]=getfa(j+1);
if (A>B) a[i]=A,vis[A]=true,fat[i]=getfa(i+1);
}
for (int i=1;i<=n;i++) if (!vis[i]) a[getfa(1)]=i;
putchar('!');for (int i=1;i<=n;i++) printf(" %d",a[i]);puts("");
return 0;
}
大佬真的厉害%%%
@lixiao189
您假假