百力滋品尝会

$N=2$ 时只有一个相邻和，因此差为 $0$。当 $N\geq3$ 时，如果所有相邻和相等，则由 $P_1+P_2=P_2+P_3$ 得到 $P_1=P_3$，矛盾。因此最优值至少为 $1$。令 $m=\lfloor(N+1)/2\rfloor$，按 $m,m+1,m-1,m+2,m-2,\ldots$ 的顺序输出范围内的数。每个数恰好出现一次，相邻和只可能为 $2m$ 或 $2m+1$，达到下界。时间复杂度为 $O(N)$，额外空间为 $O(1)$。子任务 $1$ 可以用 $O(N!N)$ 时间枚举所有排列。

Solution written by GPT6.1