本文主要是介绍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;
}这篇关于UVA - 669 Defragment的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
