题意
对于一个长度为 \(N\) 的排列 \(Q\)，定义其为好的，当且仅当
- 对于任意整数 \(i \in \left[1, N\right]\)，在进行若干次操作 \(i \leftarrow Q_i\) 后可以得到 \(i = 1\)。
给定一个排列 \(P\)，定义一次操作为交换两个数。定义 \(M\) 为可以将 \(P\) 变为一个好的的排列的最小操作次数，求在操作 \(M\) 次的情况下可以得到的字典序最小的排列。
（\(1 \le N \le 2 \times 10^5\)）。
题解
转化为图论模型，考虑对于对于所有 \(i \in \left[1, N\right]\)，建边 \(i \rightarrow P_i\)，因为每个点的出度和入度均为 \(1\)，所以建出的图一定是若干个环。而一个好的排列最后建出的图就是一个长度为 \(N\) 的环。而每次操作实质上就是合并两个环。
由于所有节点最后均与 \(1\) 在统一个环中，并且我们要求字典序最小，那么我们可以从小到大去枚举一个元素 \(i\)，若其与 \(1\) 不在同一个环中就交换其所在环的一个元素与 \(1\) 所在环的一个元素，考虑到需要字典序最小，那么我们可以交换与 \(1\) 在同一个环的所有元素中第一个大于当前元素，若与 \(1\) 在同一个环的所有元素均小于当前元素，那么我们将其与最后一个位置交换。
若出现后者的情况，可以发现与 \(1\) 联通的集合为 \(\left\{1, 2, 3, \cdots, i - 1\right\}\)，由于值的集合和下标集合相同，所以这种情况下 \(i\) 会与 \(P_{i - 1}\) 交换。若出现前者的情况，由于其是一个环，那么一定存在边 \(u \rightarrow v\) 满足， \(u < i - 1, v > i\)，即存在 \(j \le i - 1, P_j > i\)。此时的 \(j\) 一定满足对于任意 \(k < j\)，有 \(P_k < i \Rightarrow P_k < i + 1\)，也就是说被 \(i\) 排除的位置集合也不可能进入 \(i + 1\) 的决策集合，换句话说，每次交换位置的位置是单调递增的。那么我们使用一个指针 \(j\) 去维护即可，若找到了 \(P_j > i\) 或扫描到了 \(i - 1\) 那么就执行交换操作。
总复杂度 \(\mathcal{O}(N)\)，可以通过本题。
Code
#include <bits/stdc++.h>
typedef int valueType;
typedef std::vector<valueType> ValueVector;
typedef std::vector<bool> bitset;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
valueType T;
std::cin >> T;
for (int testcase = 0; testcase < T; ++testcase) {
valueType N;
std::cin >> N;
ValueVector P(N + 1), pos(N + 1);
for (valueType i = 1; i <= N; ++i) {
std::cin >> P[i];
pos[P[i]] = i;
}
valueType pointer = 1;
bitset visited(N + 1, false);
{
valueType y = pos[1];
while (!visited[P[y]]) {
visited[P[y]] = true;
y = P[y];
}
}
for (valueType i = 1; i <= N; ++i) {
if (visited[i])
continue;
valueType const x = pos[i];
while (pointer < i - 1)
if (P[pointer] < i)
++pointer;
else
break;
{
valueType y = x;
while (!visited[P[y]]) {
visited[P[y]] = true;
y = P[y];
}
}
std::swap(P[x], P[pointer]);
}
std::copy(P.begin() + 1, P.end(), std::ostream_iterator<valueType>(std::cout, " "));
std::cout << std::endl;
}
std::cout << std::flush;
return 0;
}