UVa 669 - Defragment

链接

传送门

题意

给出$k$个文件,每个文件由一些碎片组成,给出每个碎片所在的内存地址,输出将文件按照顺序连续存放的移动方法。

思路

首先处理所有空地址,将应该放过来的碎片放好,然后放置错位的放到内存结尾,继续填补空缺。

代码

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
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 10010;
int n, k, cnt;
int p[maxn], id[maxn];
void dfs(int x) {
printf("%d %d\n", p[x], x);
id[x] = x;
int tmp = p[x];
p[x] = x;
id[tmp] = 0;
if (tmp <= cnt) {
dfs(tmp);
}
}
int main() {
int t;
scanf("%d", &t);
while (t--) {
scanf("%d%d", &n, &k);
cnt = 0;
memset(p, 0, sizeof p);
memset(id, 0, sizeof id);
while (k--) {
int x;
scanf("%d", &x);
for (int i = 0; i < x; ++i) {
scanf("%d", &p[++cnt]);
id[p[cnt]] = cnt;
}
}
bool flag = true;
for (int i = 1; i <= cnt; ++i) {
if (p[i] != i) {
flag = false;
break;
}
}
if (flag) {
puts("No optimization needed");
}
for (int i = 1; i <= cnt; ++i) {
if (id[i] == 0) {
dfs(i);
}
}
for (int i = 1; i <= cnt; ++i) {
if (id[i] != i) {
printf("%d %d\n", i, n);
p[id[i]] = n;
id[n] = id[i];
id[i] = 0;
dfs(i);
}
}
if (t) {
puts("");
}
}
return 0;
}