以后一定要细心,不能再犯这个低级的错误,把WA控制在最低范围内
参考了http://www.cnblogs.com/damacheng/archive/2010/09/24/1833983.html的题目分析
题目大意:你要写一个OS,要实现磁盘碎片整理的功能。磁盘分为N个簇,一个文件可以占用K个簇,(1 <= K < N <= 10000),给出各个文件的占用磁盘的情况,也就是一个文件占用了哪些簇,想要进行碎片整理,就是把这些簇按顺序整理到磁盘的最顶部,例如给出示例:
文件1:2 3 11 12,占用了4个簇,编号为1-4。
文件2:7,占用了1个簇,编号为5。
文件3:18 5 10,占用了3个簇,编号为6-8。
初始状态是这样的,0表示未占用:
簇号: 1 2 3 4 5 6 7 8 910 11 12 13 14 15 16 17 18
逻辑编号:0 1 2 07 0 5 00 8 34 00 0 0 0 6
一共整理到最后,磁盘的情况最后是这样的:
簇号: 1 2 3 4 5 6 7 8 910 11 12 13 14 15 16 17 18
逻辑编号:1234567800000 0 0 000
写一个程序得到整理好碎片最少需要多少步操作,并把这些操作打印出来。比如说第1个簇的内容放到第2个簇,打印出1 2。操作的定义是这样的:把一个簇的内容放到另个一个簇中,算是一步操作。
注意这里是Special Judge,意思是只要答案符合要求就行了,不必和SAMPLE中的OUTPUT一样也可以AC。
怎么才能找到最少的步数呢?我想了半天也没怎么想出来,于是看了看DISCUSS,总结以下:
遍历整个磁盘,设i为当前遍历的簇的编号,clusters为整个磁盘,clusters[i]表示第i个簇是否被占用,被哪个编号的文件片段占据。
(1) 如果clusters[i]为0,也就是未被使用,不进行处理。
(2) 如果clusters[i]为i,也就是已经到了整理好的状态,不进行处理。
(3) 如果clusters[i]不满足1和2,则又有两种情况。
情况一:磁盘使用情况成链:如图所示:
簇号: 1 2 3 4 5 6...
逻辑编号:5 04230 ...
第1个簇被第5个文件片断占据,第5个簇又被第3个文件片段占据,第3个簇又被第4个文件片段占据,第4个簇又被第2个文件片断占据,第2个簇未被占据。算法就很简单了,按照簇被访问的反方向:
clusters[2] = clusters[4],clusters[4] = clusters[3],clusters[3] = clusters[5],
clusters[5] = clusters[1],最后clusters[1] = 0。怎么样反方向呢,使用一个栈就好了。
情况二:磁盘使用情况成环:如图所示:
簇号: 1 2 3 4 5 6...
逻辑编号:514230 ...
这种情况跟情况一差不多,只是最后clusters[2]指向了第1个簇,这样就形成了一个环,这里只是需要额外处理一下,就像交换2个变量一样,先在从磁盘末尾找到1个空的簇,因为题目保证至少有一个空的簇,先把clusters[2]放到这个空的簇中,然后再执行情况1中的操作,最后再把空的簇的值赋给clusters[1]就好了。最后注意一点,如果操作次数为0,则需要输出一行信息。
Source Code
Problem: 1033
|
|
User:
yangliuACMer
|
Memory: 420K |
|
Time: 704MS |
Language: C++ |
|
Result: Accepted
|
分享到:
相关推荐
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
选择了三道经典的二分查找的poj模拟题,有利于读者对二分查找的深刻把握
poj分类poj分类poj分类poj分类
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
poj2492 A Bug's Life并查集应用的扩展,希望可以给大家带来用处
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
北大POJ1159-Palindrome 解题报告+AC代码
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
poj题目2775文件子目录源代码,递归经典题目,
PKU 的online judge的题目一些分类
C语言写的,通过了.我第一个POJ通过的文件,纪念一下.POJ上对于格式要求还真是紧啊!
poj 百练 题目分类 poj 百练 题目分类
POJ1083的代码,POJ1083的代码,POJ1083的代码
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
poj 1001答案
POJ1048,加强版的约瑟夫问题 难度中等