浙江财经大学
信工学院ACM集训队

POJ 1033 Defragment

本文由 Ocrosoft 于 2016-10-31 16:49:16 发表
Defragment

Time Limit:2000MS     Memory Limit:10000KB     64bit IO Format:%lld & %llu

Description

You are taking part in the development of a “New Generation” operating system and the NG file system. In this file system all disk space is divided into N clusters of the equal sizes, numbered by integers from 1 to N. Each file occupies one or more clusters in arbitrary areas of the disk. All clusters that are not occupied by files are considered to be free. A file can be read from the disk in the fastest way, if all its clusters are situated in the successive disk clusters in the natural order. 
Rotation of the disk with constant speed implies that various amounts of time are needed for accessing its clusters. Therefore, reading of clusters located near the beginning of the disk performs faster than reading of the ones located near its ending. Thus, all files are numbered beforehand by integers from 1 to K in the order of descending frequency of access. Under the optimal placing of the files on the disk the file number 1 will occupy clusters 1, 2, …, S1, the file number 2 will occupy clusters S1+1, S1+2, …, S1+S2 and so on (here Si is the number of clusters which the i-th file occupies). 
In order to place the files on the disk in the optimal way cluster-moving operations are executed. One cluster-moving operation includes reading of one occupied cluster from the disk to the memory and writing its contents to some free cluster. After that the first of them is declared free, and the second one is declared occupied. 
Your goal is to place the files on the disk in the optimal way by executing the minimal possible number of cluster-moving operations. 

Input

The first line of the input file contains two integers N and K separated by a space(1 <= K < N <= 10000).Then K lines follow, each of them describes one file. The description of the i-th file starts with the integer Si that represents the number of clusters in the i-th file (1 <= Si < N). Then Si integers follow separated by spaces, which indicate the cluster numbers of this file on the disk in the natural order. 
All cluster numbers in the input file are different and there is always at least one free cluster on the disk. 

Output

Your program should write to the output file any sequence of cluster-moving operations that are needed in order to place the files on the disk in the optimal way. Two integers Pj and Qj separated by a single space should represent each cluster-moving operation. Pj gives the cluster number that the data should be moved FROM and Qj gives the cluster number that this data should be moved TO. 
The number of cluster-moving operations executed should be as small as possible. If the files on the disk are already placed in the optimal way the output should contain only the string “No optimization needed”. 

Sample Input

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

Sample Output

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

Solution

题意:
   比较难解释(转化一下),在一定大小(当做是 n MB)的磁盘上有m个文件,每个文件被拆成k部分,每个部分是1MB(这样比较好解释,实际情况上计算机课就知道了),分别
保存在磁盘上的某些位置,例如样例是20MB的磁盘,3个文件,第一个文件有4个部分,分别保存在2,3,11,12MB的地方。第二个文件,一个部分,保存在7MB的位置…
   其他位置都是空的,题目保证至少有1MB的空位置。题目要求进行碎片整理,把有文件的挪到磁盘前面,并且按照文件顺序排列。
   也就是说,文件1的在2,3,11,12位置的文件片段要移动到位置1,2,3,4,文件2的7位置的片段要移动到位置5,以此类推。输出移动步骤(Special Judge).
思路:
   如果对读入的文件片段进行从1到n的标号,那么标号就是这个文件碎片最终要移动到的位置。
   对于文件片段i,他要移动到位置i,如果i那里有其他片段,那么就考虑那个片段要移动到的位置,递归了…
   这样递归下去直到有一个片段要移动到的位置是空(0),那么就先把这个移动过去,再把上一个移动过来…第一个移动到目标位置,这样这一串都到达目标位置了。
   上一行的分析还要考虑,如果一直递归下去,某个片段要移动到第一个片段的位置(成环),那么就把最后的文件片段移动到磁盘末尾,按照上面的思路移动,最后把移动到
末尾的片段移动到目标位置即可。

#include <set>
#include <map>
#include <list>
#include <cmath>
#include <stack>
#include <queue>
#include <ctime>
#include <string>
#include <cstdio>
#include <vector>
#include <cctype>
#include <climits>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <functional>
#define strend string::npos
#define ms(a) memset(a,0,sizeof(a))
typedef long long LL;
const LL LINF = LLONG_MAX / 2;
const int INF = INT_MAX / 2;
const int MAXN = 10000 + 10;
const int MOD = 1000000009;
int gcd(int a, int b)
{
	if (!b)return a;
	return gcd(b, a%b);
}
using namespace std;
//or2..or2..or2..or2..//
int disk[MAXN];
//磁盘大小,文件数量,文件片段编号
int n, m, cnt = 1;
stack<int> s;
int ans = 0;
int move(int tmp)
{
	while (!s.empty())
	{
		int t = s.top(); s.pop();
		disk[tmp] = disk[t];
		printf("%d %d\n", t, tmp);
		tmp = t;
		ans++;
	}
	return tmp;
}
void solve()
{
	int tmp;
	for (int i = 1; i <= n; i++)
	{
		if (disk[i] == i)continue;//已经是目标状态,避免不必要的移动
		if (disk[i] == 0)continue;//空,不移动
		s.push(i); tmp = disk[i];
		bool flag = false;//连锁的最后一个目标位置是0,反向移动可以移动成目标状态
		//否则,将最后一个移动到空磁盘位置,反向移动后,将最后一个移回(空当接龙...)
		while (true)
		{
			if (disk[tmp] == i) { flag = true; break; }
			else if (disk[tmp] == 0) { flag = false; break; }
			s.push(tmp);
			tmp = disk[tmp];
		}
		int empty = n;
		if (flag)
		{
			//先找到一个空位置,从后往前找,避免后面的移动过程中卡住
			while (disk[empty] != 0)empty--;
			disk[empty] = disk[tmp];//先移动到空位置
			printf("%d %d\n", tmp, empty);
			tmp = move(tmp);
			disk[tmp] = disk[empty];
			disk[empty] = 0;
			printf("%d %d\n", empty, tmp);
		}
		else disk[move(tmp)] = 0;
	}
}
int main()
{
	cin >> n >> m;
	for (int i = 0; i < m; i++)
	{
		int k, t; cin >> k;
		for (int j = 0; j < k; j++)
		{
			cin >> t;
			disk[t] = cnt++;
		}
	}
	solve();
	if (ans == 0)printf("No optimization needed\n");
	return 0;
}

欢迎转载,请保留出处与链接。Ocrosoft » POJ 1033 Defragment

点赞 (0)or拍砖 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址