给一个正整数 \(n\) ，你需要构造一个 \(n\) 的排列 \(p_1, p_2, \cdots, p_n\) 。对于排列 \(p\) 的每个子段 \([l, r]\) ，\(mex_{i = l}^{r} a_i\) 的结果为质数的次数尽可能多。
此处的 \(mex\) 最小排除值最低为 \(1\) 而非 \(0\) 。
不难想到，小质数 \(2, 3\) 容易构造。
于是有贪心算法：让 \(1\) 在尽可能多的子段里，而 \(2\) 离 \(1\) 尽可能远。于是可以构造出尽可能多的 \(mex = 2\) 的子段。再让 \(3\) 离 \(2\) 尽可能远，于是可以构造出尽可能多的 \(mex = 3\) 的子段。
要使 \(1\) 在尽可能多的子段里，\(1\) 应该在 \(\lceil \frac{n}{2} \rceil\) 位置。
- 根据第 \(i\) 个元素会在 \((i - 0) \times (n - i + 1)\) 个子段中的性质
然后让 \(2\) 在 \(1\) 位置，\(3\) 在 \(n\) 位置。
此时可以观察出，除了 \([l, r]\) 这一段的 \(mex = 4\) ，所有段的 \(mex \leq 3\) 。于是上述的贪心算法可以在构造完 \(3\) 后截止。
view
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
void solve(){
int n; std::cin >> n;
if (n == 1) std::cout << "1\n";
else if (n == 2) std::cout << "1 2\n";
else {
std::vector<int> a(n+1);
a[(n+1)/2] = 1;
a[1] = 2;
a[n] = 3;
int cur = 4;
for (int i = 1; i <= n; i++) if (!a[i]) a[i] = cur++;
for (int i = 1; i <= n; i++) std::cout << a[i] << " \n"[i==n];
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen("IO/in", "r", stdin); freopen("IO/out", "w", stdout);
#endif
int _ = 1; std::cin >> _;
while (_--) solve();
return 0;
}