简要题意

给定正整数 $n$，构造一个 $1$ 至 $n$ 的排列 $p_1,p_2,\dots,p_n$ 满足以下条件：

• 对于 $1 \le i \le n$，设 $c_i = \lceil \frac{p_1+p_2+\dots +p_i}{i} \rceil$，则在 $c_1,c_2,\dots,c_n$ 中至少有 $\lfloor \frac{n}{2} \rfloor$ 个质数。

$n \le 10^4$

解法

本题有很多（乱搞）解法，这里给出一个可以严格证明的做法。

考虑将 $c$ 的一个前缀都赋值成相同的质数。这可以通过取一个质数 $p$ 并将前缀排列成 $p, p-1, p+1, p-2, p+2, \dots$，这样长度为 $2\min(p, n-p+1)-1$ 的前缀的 $c$ 值都是 $p$。

根据 Bertrand's Postulate，对于任意整数 $x$，$[x,2x]$ 内至少存在一个质数。

取其中的任意一个质数，长度 $\left(2\lfloor \frac{n}{3}\rfloor-1 \right)$ 的前缀就都是质数了。