poj 1033 Defragment-技术圈

Defragment

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.Description

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

碎片整理

描述

您正在参与“新一代”操作系统和 NG 文件系统的开发。在这个文件系统中，所有的磁盘空间被分成 N 个大小相等的簇，用 1 到 N 的整数编号。每个文件在磁盘的任意区域占据一个或多个簇。所有未被文件占用的簇都被认为是空闲的。如果文件的所有簇按自然顺序位于连续的磁盘簇中，则可以以最快的方式从磁盘读取文件。

磁盘以恒定速度旋转意味着访问其集群需要不同的时间。因此，读取位于磁盘开头附近的簇比读取位于磁盘结尾附近的簇执行得更快。因此，所有文件都预先按照访问频率从高到低的顺序用从 1 到 K 的整数编号。在磁盘上文件的最佳放置下，文件号 1 将占据簇 1、2、...、S1，文件号 2 将占据簇 S1+1、S1+2、...、S1+S2 和依此类推（这里的 Si 是第 i 个文件占用的簇数）。
为了以最佳方式将文件放在磁盘上，执行集群移动操作。一种集群移动操作包括将一个被占用的集群从磁盘读取到内存并将其内容写入某个空闲集群。之后，第一个被宣布为空闲，第二个被宣布为被占用。
您的目标是通过执行尽可能少的集群移动操作，以最佳方式将文件放置在磁盘上。

输入

输入文件的第一行包含两个整数 N 和 K，由空格分隔（1 <= K < N <= 10000）。然后是 K 行，每行描述一个文件。第 i 个文件的描述以整数 Si 开头，表示第 i 个文件中的簇数（1 <= Si < N）。然后是Si整数，后面用空格隔开，按自然顺序表示该文件在磁盘上的簇号。
输入文件中的所有簇号都不同，磁盘上总是至少有一个空闲簇。

输出

您的程序应该将任何需要的集群移动操作序列写入输出文件，以便以最佳方式将文件放置在磁盘上。由单个空格分隔的两个整数 Pj 和 Qj 应该代表每个集群移动操作。Pj 给出了数据应该从哪里移动的簇号，Qj 给出了这个数据应该移动到的簇号。
执行的集群移动操作的次数应尽可能少。如果磁盘上的文件已以最佳方式放置，则输出应仅包含字符串“无需优化”。

样本输入

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

样本输出

题意：对一个磁盘进行整理，所谓的整理就是把同一个文件的一些数据，按照次序依次的存放，问整理的时候，磁盘的替换的操作是哪一些

思路：首先如果输入的时候就像定义好，每个文件应该存放的位置，然后看看它本身的位置和存放的位置是否一致，一致则不需要进行操作，不一致在进行操作

代码：

#include 
#include 


int m,n;
bool mark[10005];   //这个是用判断有没有环。
int num[10005]; //0代表为空，-1代表匹配好
int flag;

void dfs(int x)
{
    if(!num[num[x]])   //这个则说明，num[x]可以和x进行替换
    {
        printf("%d %d\n",x,num[x]);
        num[num[x]] = -1;
        num[x] = 0;
        return;
    }
    if(mark[num[num[x]]])   //判断是否成环，如果成了环，则把最开始的那个与最后的一个进行交换 ，空出一个位置。
    {
        for(int i = m;i>0;i--)
            if(!num[i])
            {
                printf("%d %d\n",x,i);
                num[i] = num[x];
                num[x] = 0;
                return;
            }
    }
    dfs(num[x]);
    printf("%d %d\n",x,num[x]);
    num[num[x]] = -1;
    num[x] = 0;
}
int main()
{
    while(~scanf("%d%d",&m,&n))
    {
        int k,cnt = 1,tmp;
        flag = 0;
        memset(num,0,sizeof(num));
        for(int i = 0;i        {
            scanf("%d",&k);
            while(k--)
            {
                scanf("%d",&tmp);
                num[tmp]=cnt++;
                if(tmp ==cnt-1)  //不用进行交换
                    num[tmp] = -1;
            }
        }
        for(int i = 1;i<=m;i++)
        {
            if(num[i]&&num[i]!=-1)
            {
                memset(mark,false,sizeof(mark));
                flag = 1;
                mark[i] = true;
                dfs(i);
            }
        }
        if(!flag)
            printf("No optimization needed\n");
    }
    return 0;
}