题意
题目大意是在磁盘上有若干个cluster的数据,分别在不同位置,现在需要整合这些数据.
input:
20 3
4 2 3 11 12
1 7
3 18 5 10
表示在cluster 2, 3, 11, 12, 7, 18, 5, 10的位置有数据,要求通过复制这些数据,使得磁盘前面没有空闲的部分,并且不能改变这些数据的相对顺序.
output:
2 1 (cluster2处的数据复制到cluster1)
3 2
11 3
12 4
18 6
10 8
5 20
7 5
20 7
分析
- 要保证数据不丢失,在复制的时候,目标位置需要是空闲的.假设有3个cluster的数据,c1的目标位置在c2, c2的目标位置在c3,c3的目标位置是空白.那么对于c1通过深度搜索就能找到空白位置,依次复制c3,c2,c1即可.
- 可能出现的情况是成环,比如c3的目标位置在c1处,那么只需要把c1先复制到其余的任一空白处,然后复制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;
}
版权声明:本文为Hering_Linux原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。