526互联

Codeforces Round 798 (Div. 2) B. Mystic Permutation

发布时间 2023-09-10 22:00:05作者: zsxuan

给一个长为 \(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;
}