首页 > 代码库 > UVA - 669 Defragment
UVA - 669 Defragment
题意:简单说就是将第i个簇号放回i,求最少的步数
思路:只处理链形,和环形的情况,其他的可以不管,对于链形来说,只要倒置就行了,环形的找一个空闲的放一个,然后就是链形的情况了
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <stack> using namespace std; const int MAXN = 10005; int culsters[MAXN]; int culster_num, file_num; int cnt,num; stack<int> s; void cal() { int next; for (int i = 1; i <= culster_num; i++) { if (culsters[i] == i) continue; else if (culsters[i] != 0) { s.push(i); next = culsters[i]; int is_circle = 0; while (1) { if (culsters[next] == i) { is_circle = 1; break; } else if (culsters[next] == 0) { is_circle = 0; break; } s.push(next); next = culsters[next]; } int t, j; if (is_circle == 1) { for (j = culster_num; j >= 1; j--) if (culsters[j] == 0) break; printf("%d %d\n", next, j); culsters[j] = culsters[next]; while (!s.empty()) { t = s.top(); printf("%d %d\n", t, next); culsters[next] = culsters[t]; next = t; s.pop(); num++; } culsters[next] = culsters[j]; culsters[j] = 0; printf("%d %d\n", j, next); } else { while (!s.empty()) { t = s.top(); printf("%d %d\n", t, next); culsters[next] = culsters[t]; next = t; s.pop(); num++; } culsters[next] = 0; } } } if (num == 0) printf("No optimization needed\n"); } int main() { int t; scanf("%d", &t); while (t--) { scanf("%d%d", &culster_num, &file_num); memset(culsters, 0, sizeof(culsters)); cnt = 1, num = 0; for (int i = 0; i < file_num; i++) { int n, t; scanf("%d", &n); for (int j = 0; j < n; j++) { scanf("%d", &t); culsters[t] = cnt++; } } cal(); if (t) printf("\n"); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。