題意

題目大意是在磁盤上有若干個cluster的數(shù)據(jù)，分別在不同位置，現(xiàn)在需要整合這些數(shù)據(jù)．

input:

20 3
4 2 3 11 12
1 7
3 18 5 10

表示在cluster 2, 3, 11, 12, 7, 18, 5, 10的位置有數(shù)據(jù)，要求通過復(fù)制這些數(shù)據(jù)，使得磁盤前面沒有空閑的部分，并且不能改變這些數(shù)據(jù)的相對順序．

output:

2 1 (cluster2處的數(shù)據(jù)復(fù)制到cluster1)
3 2
11 3
12 4
18 6
10 8
5 20
7 5
20 7

分析

• 要保證數(shù)據(jù)不丟失，在復(fù)制的時候，目標(biāo)位置需要是空閑的．假設(shè)有３個cluster的數(shù)據(jù)，c1的目標(biāo)位置在c2, c2的目標(biāo)位置在c3，c3的目標(biāo)位置是空白．那么對于c1通過深度搜索就能找到空白位置，依次復(fù)制c3，c2，c1即可．
• 可能出現(xiàn)的情況是成環(huán)，比如c3的目標(biāo)位置在c1處，那么只需要把c1先復(fù)制到其余的任一空白處，然后復(fù)制c3，c2，最后是c1．

代碼如下：
Memory: 1404K　Time: 797MS　Length: 70LINES

#include <cstring> #include <iostream> using namespace std;int rear = 0; void search(int* clusters, bool* flag, int max_cluster, int idx) {if (flag[clusters[idx]]) {for (int i = max_cluster; i > 0; --i) {if (clusters[i] == 0) {cout << idx << " " << i << endl;clusters[i] = clusters[idx];clusters[idx] = 0;rear = i;return;}}}if (clusters[clusters[idx]] != 0) {flag[idx] = true;search(clusters, flag, max_cluster, clusters[idx]);}cout << idx << " " << clusters[idx] << endl;clusters[clusters[idx]] = clusters[idx];clusters[idx] = 0;flag[idx] = false; }int main() {int max_cluster = 0;int files = 0;cin >> max_cluster >> files;int* clusters = new int[max_cluster + 1];memset(clusters, 0, sizeof(int) * (max_cluster + 1));bool* flag = new bool[max_cluster + 1];memset(flag, 0, sizeof(bool) * (max_cluster + 1));int cnt = 0;int right = 0;int cluster_idx = 0;for (int i = 0; i < files; ++i) {cin >> cnt;for (int j = 0; j < cnt; ++j) {int src = 0;cin >> src;clusters[src] = ++cluster_idx;if (src == cluster_idx) {++right;}}}if (right == cluster_idx) {cout << "No optimization needed" << endl;} else {for (int i = 1; i < max_cluster + 1; ++i) {if (clusters[i] != 0 && clusters[i] != i) {search(clusters, flag, max_cluster, i);if (rear) {cout << rear << " " << clusters[rear] << endl;clusters[clusters[rear]] = clusters[rear];clusters[rear] = 0;rear = 0;}}}}delete[] clusters;delete[] flag;return 0; }

總結(jié)

以上是生活随笔為你收集整理的POJ 1033--Defragment的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。