Codeforces 844C(DFS)

Codeforces 844C
题意:给你一个序列,这个是序列是乱序的,你需要把它给排序,你有k个桶,每个数放入桶以后就会自动排序,然后再把这些数按原来的位置按现在的顺序放入,使得这个序列变得有序。问最大的k为多少?

先对原数组进行离散化,然后就得到一个1到$n$的排列。每个数要排到相应为位置(即$i=a[i]$),那么我们逐位DFS,每次DFS该位上的数值。因为$i$位置上的数$a[i]$是要被操作到$a[i]$位置上的,所以这次选的桶必须要选择$a[i]$。然后到了$a[i]$位置按照此过程继续走,直到之后走到的位置之前走过,就能停止了,这时只需要输出所有经过的节点就行,用set存比较好,自动拍好了序。由于操作次数要第一行输出,所以要用$n$个vector存答案,具体看代码的实现。

Codeforces Submission

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<set>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 100000 + 5;
int n, a[MAXN], tmp[MAXN], vis[MAXN], ans;
vector<int> step[MAXN];
set<int> s;
void dfs(int u) {
if (vis[a[u]] == -1) return ;
//DFS到该位上的数值a[u]
if (vis[a[u]] == 0) s.insert(a[u]), vis[a[u]] = 1, dfs(a[u]); else {
step[++ans].push_back(s.size());
for (set<int>::iterator it = s.begin(); it != s.end(); it++) {
step[ans].push_back(*it), vis[*it] = -1;
}
s.clear();
}
}
void clean() {
ans = 0, ms(vis, 0);
}
void solve() {
clean();
for (int i = 1; i <= n; i++) scanf("%d", &a[i]), tmp[i] = a[i];
sort(tmp + 1, tmp + 1 + n);
int nx = unique(tmp + 1, tmp + 1 + n) - tmp - 1;
for (int i = 1; i <= n; i++) a[i] = lower_bound(tmp + 1, tmp + 1 + nx, a[i]) - tmp;
for (int i = 1; i <= n; i++) dfs(i);
printf("%d\n", ans);
for (int i = 1; i <= ans; i++) {
for (int j = 0; j < (int)step[i].size(); j++) {
printf("%d ", step[i][j]);
}
printf("\n");
}
}
int main() {
scanf("%d", &n), solve();
return 0;
}

------ 本文结束 ------