UVa 669 - Defragment

发表于 分类于 ， ， Disqus：

链接

传送门

题意

给出\(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;
}
相关文章