2023 年浙江预赛

解答

考虑一个长度为 $r\ge 2$ 的循环，其元素从小到大为 $x_1<\cdots <x_r$。沿循环的有向边从 $x_1$ 走到 $x_r$ 至少累计增加 $x_r-x_1$，从 $x_r$ 回到 $x_1$ 至少累计减少同样多，故该循环贡献至少

若排列有 $c$ 个循环，则总和至少为 $2(n-c)$。因每个循环长度至少为 $2$，有 $c\le \lfloor n/2\rfloor$。

若 $n$ 为偶数，最小值至少为 $n$。排列

达到它。要取等，必须有 $n/2$ 个二循环，且每个二循环的两个数相邻；从最小未用整数开始即被迫与下一个整数配对，因此仅有这 $1$ 个排列。

若 $n$ 为奇数，最小值至少为 $n+1$。取一个连续三元组作三循环，其余相邻配成二循环即可达到。等号时循环数必须为 $(n-1)/2$，故恰有一个三循环，其余全为二循环；每个循环的元素还必须连续。三元组只能是

共有 $(n-1)/2$ 种位置，每个三元组有两个方向的三循环，故共有 $n-1$ 个排列。

综上，最小值与排列数分别为