猜排列（easy）

算法思路

先确定一个位置的值，再利用两数之和恢复其他位置。

首先询问 $(1,2)$、$(1,3)$、$(2,3)$，分别得到

$$s_{12}=a_{1}+a_{2},\qquad s_{13}=a_{1}+a_{3},\qquad s_{23}=a_{2}+a_{3}.$$

将前两个回答相加，再减去第三个回答，可以消去 $a_{2},a_{3}$：

$$s_{12}+s_{13}-s_{23}=2a_{1}.$$

因此，前三个位置的值为

$$a_{1}=\frac{s_{12}+s_{13}-s_{23}}{2},\qquad a_{2}=s_{12}-a_{1},\qquad a_{3}=s_{13}-a_{1}.$$

对于每个 $i=4,5,\ldots,n$，询问 $(1,i)$。设回答为 $s$，则 $a_{i}=s-a_{1}$。恢复所有位置后，输出整个排列。

正确性证明

前三次询问的回答满足上述等式，因此计算得到的 $a_{1},a_{2},a_{3}$ 均为真实值。

对于其余位置 $i$，询问返回 $s=a_{1}+a_{i}$。由于 $a_{1}$ 已被正确确定，故 $s-a_{1}$ 恰好等于真实的 $a_{i}$。

因此，算法能够正确恢复整个排列。

复杂度分析

前三个位置使用 $3$ 次询问，其余 $n-3$ 个位置各使用一次询问，总询问次数为

$$3+(n-3)=n,$$

满足题目限制。

时间复杂度为 $O(n)$，存储整个排列的空间复杂度为 $O(n)$。