题目描述你要把磁盘的文件碎片整理一下包含了n个块1~n)它们分别属于k个文件文件中的块移动的时候相对顺序不能改变什么叫做相对顺序不能改变文件A 由 3个块组成的 原来的顺序 块1 块2 块3 现在你可以把这三块移动到磁盘的不同位置移动后要保证 块1 在块2之前块2在块3之前举一个例子你有一个书架上面有n个格子 编号是1~n每一个格子里面本来应该放一本固定编号的书现在书被放乱了需要你整理这些书你可以分成k组原来的前后顺序不能改变3本语文书1 2 3整理之后保证 1 6 7 2 0 9 3怎么去整理假设书架有一个空格子我们可以把这本书先放这里再去移动其他的书每一次移动一本书到空位就是一次操作20342311121731851020个磁盘3个文件 文件1:{2,3,11,12}文件2:{7}文件3{18,5,10}2—13-211-312-47-518-65-710-81,4,6,8是空闲的11-3-2-1终点空闲312-4118-6110-817-5-73图论模型问题构建一个映射关系 i号块当前所在的位置记录a[i]a[i]a[i], 把i号 放在 i的位置a[1]3 1号块被放在3的位置 位置1有一条边指向了3发现 形成 多个独立的集合 单点 a[i]i 集合长度2需要去整理最少的移动次数 集合长度1 的总和/9#includebits/stdc.husingnamespacestd;constintN1e510;intn,k,s,sum,ans,a[N],vis[N];//x 当前的位置编号 a[x] : x应该放在哪里 a[3]5,目前放在3最终去5intdfs(intx){if(!x||vis[x])returnx;vis[x]1;ans;returndfs(a[x]);}intmain(){cinnk;for(inti1;ik;i){cins;for(intj1;js;j){cina[sumj];if(a[sumj]sumj)vis[sumj]1;}sums;}for(inti1;isum;i){if(vis[i])continue;if(dfs(a[i])a[i])ans;}if(ans)coutWe need ans move operations.;elsecoutNo optimization needed.;return0;}