Defragment
Time Limit : 4000/2000ms (Java/Other) Memory Limit : 20000/10000K (Java/Other)
Total Submission(s) : 6 Accepted Submission(s) : 3
Special Judge
Problem 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
Source
PKU
题目大意：正如题目名字一样，是模拟电脑内存的碎片整理，在已知内存大小的范围中，有K堆带有编号的碎片随意放置。让你设计一个程序处理，把这些碎片
按照其编号，从小到大依次排好，求出其移动的最小步骤。
第一行输入两个数据N和K，第一个数据N表示内存的空间大小范围是1~N。第二个数据K表示有三堆文件碎片。
从第二行到第K+1行表示该堆文件的碎片，第一个数据为，该堆文件碎片的个数S，然后输入S个数据，每个数据代表的是其碎片的位置，以下同理。
在这里需要明白的是，你第一堆文件输入的第一个碎片数据，该数据是代表编号1的碎片在内存中的位置。
如样例：
内存空间的范围： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
碎片编号： 1 2 7 5 8 3 4 6
输入完毕，代表当前碎片的编号在内存中所在的位置，而目的位置为：
内存空间的范围： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
碎片编号： 1 2 3 4 5 6 7 8
每次操作只能移动一次，而且每次移动只能把有碎片的位置，移动到空的位置上。求出的最少步骤次数，并且显示出，移动时候的过程、这一题目是有
多中最优解，所以，最小移动次数的移动步骤可能不一样也是行的通的。(注意观察这题是有特殊判定的。)
分析：在这一题中，需要自己去多多设计几组样例，自己去运算下，就可以知道该如何入手。该题目是想要把碎片的编号移到其所对用的位置上。在移动
的操作上，无非需要解决的只有两个问题，一个数碎片的编号，与其所在的位置关系，一个递推一个，可能构成的是环，或者可能构成的事链。最后
需要注意的就是，如果给你的碎片位置都已经是匹配完的，不需要进行任何操作，只需输出“ No optimization needed”。只需要解决这两方面的问题即可。
具体的过程就看代码了，不多加解释。
1 #include2 #include 3 #include 4 int num[101000],N,Max_NUM,T； 5 int Stand[101000];/*保存递推的数据*/ 6 int Flash;/*记录成功匹配位置的个数*/ 7 put()/*验证输出内存相对位置的碎片编号，检验是否移动正确*/ 8 { 9 int ii; 10 putchar(10); 11 for(ii=1;ii<=N;ii++) 12 printf("%d ",num[ii]); 13 putchar(10); 14 } 15 16 int Find_O(int n)/*寻找n位置上的碎片编号*/ 17 { 18 int i=0,j=num[n],k,sign; 19 Stand[i++]=n; 20 while(j!=n&&j!=0)/*递推n位置上的碎片编号的关系，*/ 21 { /*直到找到0，或者n本身该结束递推*/ 22 Stand[i++]=j;/*找到0说明与该位置相关的碎片编号依次递推下去是条链*/ 23 j=num[j]; /*找到n说明与该位置相关的碎片编号依次递推下去是个环*/ 24 } 25 Flash+=i; /*累加移动的数据个数，因为该些数据在下部操作将都会被移动到正确位置*/ 26 if(j==n) /*如果是环的情况，需要找到一个空位置，然后完成移动的操作*/ 27 { 28 for(k=N;k>=1;k--) 29 if(num[k]==0) 30 { 31 sign=k; 32 while(i!=0) 33 { 34 num[sign]=num[Stand[--i]]; 35 printf("%d %d\n",Stand[i],sign); 36 sign=Stand[i]; 37 num[sign]=0; 38 } 39 num[n]=num[k]; 40 num[k]=0; 41 printf("%d %d\n",k,n); 42 break; 43 } 44 } 45 else if(j==0) /*如果是链的情况，只需要找到n所对应的的位置，然后完成移动的操作*/ 46 { 47 for(k=N;k>=1;k--) 48 if(num[k]==n) 49 { 50 sign=k; 51 while(i>=2) 52 { 53 num[Stand[i-1]]=num[Stand[i-2]]; 54 num[Stand[i-2]]=0; 55 printf("%d %d\n",Stand[i-1],Stand[--i]); 56 } 57 num[n]=num[k]; 58 num[k]=0; 59 printf("%d %d\n",k,n); 60 break; 61 } 62 } 63 return 0; 64 } 65 66 void Find_N()/*这是用来初始判断该碎片整理是否都移动到所对应的的位置*/ 67 { 68 int i; 69 for(i=1;i