给一个长为 \(n\) 的排列 \(p\) ，需要构造一个长为 \(n\) 的排列 \(q\) ，满足 \(\forall i, p_i \neq q_i\) ，且 \(q\) 在所有合法排列中字典序最小。
观察一：\(n = 1\) 时无解，否则有解。
观察二：\(n > 1\) 时，\(1 \sim n - 1\) 的位置可以贪心构造，在保证字典序最小的情况下，正确性也保证。
- 排列对应的字典序最小为值最小，又不会重复，则使用 \(set\) 。
- 用指针 \(i\) 扫 \([1, n - 1]\) ，取 \(it = begin\) ，若 \(*it \neq p_i\) ，则 \(q_i = *it\) ，否则 \(q_i = *next(it)\) 。同时保证当前字典序最小和正确性。
观察三：\(ans_n\) 只剩一个数，只能填入。此时保证 \(\forall i \in[1, n - 1], q_i \neq p_i\) 情况下，\(q\) 的字典序最小。
- 若 \(q_n \neq p_n\) ，\(q\) 即答案。
- 若 \(q_n = p_n\) ，则 \(swap(q_{n - 1}, q_{n})\) 。此时保证 \(\forall i \in[1, n], q_i \neq p_i\) 情况下，\(q\) 的字典序最小。
- 已知一个排列 \(p\) ， \(swap(p_{n - 1}, p_{n})\) 后的 \(p'\) 是 \(p\) 在康托展开序的严格下一位。
view
#include <bits/stdc++.h>
void solve() {
int n; std::cin >> n;
std::vector<int> p(n+1);
std::set<int> px;
for (int i = 1; i <= n; px.insert(i), i++) std::cin >> p[i];
if (n == 1) {
std::cout << -1 << '\n';
}
else {
std::vector<int> q(n+1);
for (int i = 1; i < n; i++) {
auto it = px.begin();
if (*it != p[i]) q[i] = *it, px.erase(it);
else q[i] = *std::next(it), px.erase(std::next(it));
}
q[n] = *px.begin();
if (q[n] == p[n]) std::swap(q[n-1], q[n]);
for (int i = 1; i <= n; i++) std::cout << q[i] << " \n"[i==n];
}
}
signed main() {
int _ = 1; std::cin >> _;
while (_--) solve();
return 0;
}