题目链接
https://atcoder.jp/contests/arc167/tasks/arc167_d
题目大意
给定一个 \(1\) 到 \(n\) 的排列 \(P\) 。
定义一个排列 \(Q\)
为好排列当且仅当对于任意整数 \(1\le x \le
n\) ，通过若干次赋值（可以为 \(0\) 次） \(x
\leftarrow Q_x\) ，最终能够使得 \(x\) 变成 \(1\) 。
现在可以进行若干次操作，每次可以交换 \(P\) 的任意两个不同的位置。
假设最少进行 \(m\) 次操作使得 \(P\) 成为一个好排列，求进行 \(m\) 操作之后 \(P\) 能够成为的字典序最小的好排列。
数据范围
- \(\sum n \le 2 \times 10 ^
{5}\)
解题思路
（不想好好写了）
转化成 \(p_i \rightarrow i\)
的图模型分析一下即可。
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
| void solve() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> suf[i];
pre[suf[i]] = i;
}
set<int> circle, oth;
for (int i = 1; i <= n; i++) {
oth.insert(i);
}
oth.erase(1);
int x = 1;
while (suf[x] != 1) {
x = suf[x];
oth.erase(x);
}
for (int i = 1; i <= n; i++) {
assert(oth.find(i) == oth.end());
if (oth.empty()) {
break;
}
int mnx = *oth.begin();
if (mnx > suf[i] && i + SZ(oth) < n) {
continue;
}
int cur = mnx;
oth.erase(cur);
while (suf[cur] != mnx) {
cur = suf[cur];
oth.erase(cur);
}
suf[pre[mnx]] = suf[i];
pre[suf[i]] = pre[mnx];
suf[i] = mnx;
pre[mnx] = i;
}
vector<int> ans(n + 1);
x = 1;
do {
ans[x] = suf[x];
x = suf[x];
} while (x != 1);
for (int i = 1; i <= n; i++) {
printf("%d ", ans[i]);
}
printf("\n");
}
int main() {
int T;
cin >> T;
while (T--) {
solve();
}
return 0;
}
|