P1289 磁盘碎片整理【洛谷算法习题】

P1289 磁盘碎片整理网页链接P1289 磁盘碎片整理题目描述出于最高安全性考虑司令部采用了特殊的安全操作系统该系统采用一个特殊的文件系统。在这个文件系统中所有磁盘空间都被分成了相同尺寸的N NN块用整数1 11到N NN标识。每个文件占用磁盘上任意区域的一块或多块存储区未被文件占用的存储块被认为是可是用的。如果文件存储在磁盘上自然连续的存储块中则能被以最快的速度读出。因为磁盘是匀速转动的所以存取上面不同的存储块需要的时间也不同。读取磁盘开头处的存储块比读取磁盘尾处的存储块快。根据以上现象我们事先将文件按其存取频率的大小用整数1 11到K KK标识。按文件在磁盘上的最佳存储方法1 11号文件将占用1 , 2 , ⋯ , S 1 1,2,\cdots,S_11,2,⋯,S1​的存储块2 22号文件将占用S 1 1 , S 1 2 , ⋯ , S 1 S 2 S_11,S_12,\cdots, S_1S_2S1​1,S1​2,⋯,S1​S2​的存储块以此类推S i S_iSi​是被第i ii个文件占用的存储块的个数。为了将文件以最佳形式存储在磁盘上需要执行存储块移动操作。一个存储块移动操作包括从磁盘上读取一个被占用的存储块至内存并将它写入其他空的存储块然后宣称前一个存储块被释放后一个存储块被占用。本程序的目的是通过执行最少次数的存储块移动操作将文件按最佳方式存储到磁盘上注意同一个文件的存储块在移动之后其相对次序不可改变。输入格式每个磁盘说明的第一行包含两个用空格隔开的整数N NN和K ( 1 ≤ K ≤ N ≤ 10 5 ) K(1 \le K \le N \le 10^5)K(1≤K≤N≤105)接下来的K KK行每行说明一个文件对第i ii个文件的说明是这样的首先以整数S i S_iSi​开头表示第i ii个文件的存储块数量1 ≤ S i ≤ N − K 1 \le S_i \le N-K1≤Si​≤N−K然后跟S i S_iSi​个整数每个整数之间用空格隔开表示该文件按自然顺序在磁盘上占用的存储块的标识。所有这些数都介于1 11和N NN之间包括1 11和N NN。一个磁盘说明中所有存储块的标识都是不同的并且该盘至少有一个空的存储块。输出格式对于每一个磁盘说明只需输出一行句子“ We need M move operations. ” \text{\texttt{We need \textrm{\textit{M}} move operations.}}“We needMmove operations.”M MM表示将文件按最佳方式存储到磁盘上所需进行的最少存储块移动操作次数。如果文件已按最佳方式存储仅需输出“ No optimization needed. ” \text{\texttt{No optimization needed.}}“No optimization needed.”。输入输出样例 #1输入 #120 3 4 2 3 11 12 1 7 3 18 5 10输出 #1We need 9 move operations.解题思路本题核心是置换环统计将磁盘整理问题转化为经典的置换环求解最小移动次数。首先计算所有文件占用的总块数pos文件的最佳存储位置为1~pos即第i个位置的目标存储块为i。遍历所有存储块已在目标位置a[i]i的块无需移动剩余未归位的块会形成若干置换环每个环内的所有块都需要移动调整所有环的长度之和即为最小移动总次数。若移动次数为0输出无需优化否则输出移动次数。算法时间复杂度O ( N ) O(N)O(N)高效适配N ≤ 10 5 N \le 10^5N≤105的数据范围。总结核心逻辑磁盘块归位问题等价于置换环问题正确归位的块无需移动总移动次数为置换环长度之和。关键操作计算总占用块数、标记已归位块、遍历统计置换环长度。效率保障线性遍历处理数据无冗余计算完美满足题目大数据约束。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e55;constll INF1e18;constll M1e610;constll mod1e97;ll n,k,s,a[N],pos,ans,vis[N];llfind(ll x){if(!x||vis[x])returnx;vis[x]1;ans;returnfind(a[x]);}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cinnk;for(ll i1;ik;i){cins;for(ll j1;js;j){cina[pos];if(a[pos]pos)vis[pos]1;}}for(ll i1;ipos;i){if(vis[i])continue;ll lastfind(a[i]);if(lasta[i])ans;}if(ans)coutWe need ans move operations.endl;elsecoutNo optimization needed.endl;return0;}