磁盘碎片整理

磁盘碎片整理 源程序名 DEFRAG.??? (PAS,C,CPP) 可执行文件名 DEFRAG.EXE 输入文件名 DEFRAG.IN 输出文件名 DEFRAG.OUT 出于最高安全性考虑，司令部采用了特殊的安全操作系统，该系统采用一个特殊的文件系统。在这个文件系统中所有磁盘空间都被分成了相同尺寸的N块，用整数1到N标识。每个文件占用磁盘上任意区域的一块或多块存储区，未被文件占用的存储块被认为是可使用的。如果文件存储在磁盘上自然连续的存储块中，则能被以最快的速度读出。 因为磁盘是匀速转动的，所以存取上面不同的存储块需要的时间也不同。读取磁盘开头处的存储块比读取磁盘结尾处的存储块快。根据以上现象，我们事先将文件按其存取频率的大小用整数1到K标识。按文件在磁盘上的最佳存储方法，1号文件将占用1,2,„,S1的存储块，2号文件将占用S1+1,S1+2,...,S1+S2的存储块，以此类推(Si是被第i个文件占用的存储块的个数)。为了将文件以最佳形式存储在磁盘上，需要执行存储块移动操作。一个存储块移动操作包括从磁盘上读取一个被占用的存储块至内存并将它写入其它空的存储块，然后宣称前一个存储块被释放，后一个存储块被占用。 本程序的目的是通过执行最少次数的存储块移动操作，将文件按最佳方式存储到磁盘上，注意同一个文件的存储块在移动之后其相对次序不可改变。 输入 每个磁盘说明的第一行包含两个用空格隔开的整数N和K，1<=K<=N<=100000，接下来的K行每行说明一个文件，对第i个文件的说明是这样的:首先以整数Si开头，表示第i个文件的存储块数量，1<=Si<=N-K，然后跟Si个整数，每个整数之间用空格隔开，表示该文件按自然顺序在磁盘上占用的存储块的标识。所有这些数都介于1和N之间，包括1和N。 一个磁盘说明中所有存储块的标识都是不同的，并且该盘至少有一个空的存储块。 输出 对于每一个磁盘说明，只需输出一行句子"We need M move operations"，M表示将文件按最佳方式存储到磁盘上所需进行的最少存储块移动操作次数。如果文件已按最佳方式存储，仅需输出“No optimization needed.”。 样例 DEFRAG.IN 20 3 4 2 3 11 12 1 7 3 18 5 10 DEFRAG.OUT We need 9 move operations.