题解 CF1407C 【Chocolate Bunny】
rui_er
2020-09-09 16:18:39
交互题最好玩♂了！（雾）
题意简述：有一个 $n$ 个数的排列，每次询问 $x,y$ 得到 $a_x\bmod a_y$ 的值，最多使用 $2\times n$ 次询问，猜出这个序列。
---
思路：
看到最多 $2\times n$ 次询问，我们想到了什么？凭我们的直觉，这就是明摆着的提示要询问 $i,j$ 和 $j,i$ 啊！那怎么询问呢？
我们知道对于 $a\lt b$，$a\bmod b=a$，可以得到下面结论：
**结论**：$(a\bmod b\gt b\bmod a)\iff (a\lt b)$。
简单证明：
$$
\begin{aligned}
\operatorname{if}\ a\gt b\ &\operatorname{then}\ (a\bmod b)\lt(b\bmod a)=b\\
\operatorname{if}\ a=b\ &\operatorname{then}\ (a\bmod b)=(b\bmod a)=0\\
\operatorname{if}\ a\lt b\ &\operatorname{then}\ (b\bmod a)\lt(a\bmod b)=a
\end{aligned}
$$
在知道这个性质之后，我们就可以想到询问的方法：
设 $ma$ 为 $a_1\sim a_i$ 中最大的数的下标（大小可根据上面的结论判断），每次询问 $ma,i$ 和 $i,ma$，判断两个结果哪个更大，更新偏小的那个下标的值及最大数的下标。
最后剩下一个 $a_{ma}$ 没有值，由于数列是 $1\sim n$ 的一个排列，因此这个最大的数就是 $n$。
总询问次数 $2\times n-2$。
---
代码：
```cpp
//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4+5;
int n, a[N], ma = 1;
int ask(int x, int y) {
int _;
printf("? %d %d\n", x, y);
fflush(stdout);
scanf("%d", &_);
return _;
}
int main() {
scanf("%d", &n);
for(int i=2;i<=n;i++) {
int _1 = ask(ma, i);
int _2 = ask(i, ma);
if(_1 > _2) {
a[ma] = _1;
ma = i;
}
else a[i] = _2;
}
a[ma] = n;
putchar('!');
for(int i=1;i<=n;i++) printf(" %d", a[i]);
return 0;
}
```