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_1+1,S_1+2,\cdots, S_1+S_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
输入 #1
20 3 4 2 3 11 12 1 7 3 18 5 10输出 #1
We 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的数据范围。
总结
核心逻辑：磁盘块归位问题等价于置换环问题，正确归位的块无需移动，总移动次数为置换环长度之和。
关键操作：计算总占用块数、标记已归位块、遍历统计置换环长度。
效率保障：线性遍历处理数据，无冗余计算，完美满足题目大数据约束。
代码内容
#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e5+5;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;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);cin>>n>>k;for(ll i=1;i<=k;i++){cin>>s;for(ll j=1;j<=s;j++){cin>>a[++pos];if(a[pos]==pos)vis[pos]=1;}}for(ll i=1;i<=pos;i++){if(vis[i])continue;ll last=find(a[i]);if(last==a[i])ans++;}if(ans)cout<<"We need "<<ans<<" move operations."<<endl;elsecout<<"No optimization needed."<<endl;return0;}