题目分析

我们需要构造一个长度为 $n$ 的排列 $p_1, p_2, \dots, p_n$，使得对于每个前缀，定义

$$c_i = \left\lceil \frac{p_1 + p_2 + \dots + p_i}{i} \right\rceil $$

则在 $c_1, c_2, \dots, c_n$ 中，至少有 $\left\lfloor \frac{n}{3} \right\rfloor - 1$ 个质数。

$n$ 最大可达 $10^5$，要求我们在线性时间内构造出这样的排列。

---

核心思路

题解和标程都基于一个关键的数学定理：

伯特兰-切比雪夫定理（Bertrand's postulate）：

对于任意正整数 $x$，区间 $(x, 2x]$ 内至少存在一个质数。

利用这个定理，我们可以找到一个合适的质数 $p$，然后通过巧妙的构造，使得许多前缀的平均值恰好等于 $p$，从而产生大量的质数 $c_i$。

---

构造方法详解

第一步：选择质数 $p$

我们需要选择一个质数 $p$，使得它在排列中能够产生足够多的 $c_i = p$。

观察发现：如果我们让排列的前若干项关于 $p$ 对称，即

$$p,\ p-1,\ p+1,\ p-2,\ p+2,\ \dots$$

那么前 $2k+1$ 项的和为

$$p + (p-1) + (p+1) + \dots + (p-k) + (p+k) = (2k+1)p $$

因此平均值为 $p$，所以

$$c_{2k+1} = \left\lceil \frac{(2k+1)p}{2k+1} \right\rceil = p $$

也就是说，所有奇数下标的前缀平均值都等于 $p$。

第二步：确定 $p$ 的范围

为了使对称构造能持续足够长的时间，我们需要 $p$ 离边界不太近，即 $p - k \ge 1$ 且 $p + k \le n$。

如果我们取 $k = \left\lfloor \frac{n}{3} \right\rfloor$，那么需要：

• $p - \left\lfloor \frac{n}{3} \right\rfloor \ge 1$，即 $p \ge \left\lfloor \frac{n}{3} \right\rfloor + 1$
• $p + \left\lfloor \frac{n}{3} \right\rfloor \le n$，即 $p \le n - \left\lfloor \frac{n}{3} \right\rfloor$

注意到 $n - \left\lfloor \frac{n}{3} \right\rfloor = \left\lceil \frac{2n}{3} \right\rceil$，因此 $p$ 应满足

$$\left\lfloor \frac{n}{3} \right\rfloor < p \le \left\lceil \frac{2n}{3} \right\rceil $$

第三步：证明 $p$ 的存在性

由伯特兰-切比雪夫定理，取 $x = \left\lfloor \frac{n}{3} \right\rfloor$，则存在质数 $p$ 满足

$$\left\lfloor \frac{n}{3} \right\rfloor < p \le 2\left\lfloor \frac{n}{3} \right\rfloor $$

而 $2\left\lfloor \frac{n}{3} \right\rfloor \le \left\lceil \frac{2n}{3} \right\rceil$，因此这样的 $p$ 一定存在。

第四步：构造排列

选定质数 $p$ 后，按照以下方式构造排列：

1. 先放置 $p$
2. 然后交替放置 $p-1, p+1, p-2, p+2, \dots$，只要数值在 $[1, n]$ 范围内
3. 最后将剩余未使用的数按任意顺序放在末尾

这样构造的排列中，前 $2\left\lfloor \frac{n}{3} \right\rfloor - 1$ 个奇数下标的前缀平均值都等于 $p$，因此至少有 $\left\lfloor \frac{n}{3} \right\rfloor$ 个 $c_i$ 等于 $p$，即至少有 $\left\lfloor \frac{n}{3} \right\rfloor$ 个质数，满足题目要求（题目要求 $\left\lfloor \frac{n}{3} \right\rfloor - 1$ 个）。

---

标程实现

标程的实现思路略有不同，在 $\frac{n}{2}$ 附近寻找质数，而不是在 $\frac{n}{3}$ 到 $\frac{2n}{3}$ 区间。

#include <bits/stdc++.h>
using namespace std;

bool isPrime(int x) {
    if (x <= 1) return false;
    for (int i = 2; i * i <= x; ++i) {
        if (x % i == 0) return false;
    }
    return true;
}

vector<int> generateSol(int n, int p) {
    vector<int> ans;
    ans.push_back(p);
    for (int i = 1; i <= n; ++i) {
        if (p - i > 0) ans.push_back(p - i);
        if (p + i <= n) ans.push_back(p + i);
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    
    while (t--) {
        int n;
        cin >> n;
        
        vector<int> ans;
        // 从 n/2 开始向两侧寻找质数
        for (int x = 0; ; ++x) {
            int candidate1 = n / 2 - x;
            if (candidate1 >= 2 && isPrime(candidate1)) {
                ans = generateSol(n, candidate1);
                break;
            }
            
            int candidate2 = n / 2 + x;
            if (candidate2 <= n && isPrime(candidate2)) {
                ans = generateSol(n, candidate2);
                break;
            }
        }
        
        for (int i = 0; i < n; ++i) {
            cout << ans[i] << " \n"[i == n - 1];
        }
    }
    
    return 0;
}

为什么这样也能工作？

1. 质数存在性：在 $\frac{n}{2}$ 附近同样存在质数（由伯特兰-切比雪夫定理可得）
2. 对称构造：当 $p \approx \frac{n}{2}$ 时，左右各有约 $\frac{n}{2}$ 个整数可用，可以生成更多 $c_i = p$
3. 要求宽松：题目只要求 $\left\lfloor \frac{n}{3} \right\rfloor - 1$ 个质数，$\frac{n}{2}$ 附近的 $p$ 产生的质数数量远超这个要求

构造过程示例

以 $n = 5$，$p = 2$（$\frac{n}{2} = 2.5$，取 $2$）为例：

1. 初始：$ans = [2]$
2. $i = 1$：$p-1=1$ 加入，$p+1=3$ 加入 → $[2,1,3]$
3. $i = 2$：$p-2=0$ 无效，$p+2=4$ 加入 → $[2,1,3,4]$
4. $i = 3$：$p-3=-1$ 无效，$p+3=5$ 加入 → $[2,1,3,4,5]$

最终排列为 $[2,1,3,4,5]$，计算 $c_i$：

• $c_1 = \lceil 2/1 \rceil = 2$（质数）
• $c_2 = \lceil 3/2 \rceil = 2$（质数）
• $c_3 = \lceil 6/3 \rceil = 2$（质数）
• $c_4 = \lceil 10/4 \rceil = 3$（质数）
• $c_5 = \lceil 15/5 \rceil = 3$（质数）

全部 5 个数都是质数，远超 $\left\lfloor 5/3 \right\rfloor - 1 = 1$ 的要求。

---

时间复杂度分析

• 寻找质数 $p$：从 $\frac{n}{2}$ 开始向两侧检查，每次检查 $O(\sqrt{p})$，由于质数密度高，通常几次就能找到，总复杂度 $O(\sqrt{n})$
• 构造排列：$O(n)$
• 总复杂度 $O(n)$ 每组数据，可以轻松通过 $n \le 10^5$ 的测试

---

总结

本题的关键在于：

1. 利用伯特兰-切比雪夫定理保证在指定区间存在质数
2. 通过对称构造让多个前缀平均值等于该质数
3. 标程选择 $\frac{n}{2}$ 附近的质数，虽然与题解区间不同，但同样有效且实现更简洁

这种构造方法体现了算法竞赛中常见的"存在性构造"思想：不追求最优解，只要求找到一个满足条件的解，通常需要巧妙的数学观察。