题解：P1289 磁盘碎片整理

Eterna · 2024-07-31 10:18:32 · 题解

题目一看就不想写了，太长了。

但是读懂后，发现并不难。

只需要使用类似模拟的方法就行了。

对每一块磁盘，如果它正确的位置上在别的地方，那么就要递归遍历。

递归可以循环代替。

代码

#include<bits/stdc++.h>
#define N 1000005
using namespace std;
int a[N];
bool vis[N];
int s,k,n,m=0,ans=0;
int main()
{
    cin>>n>>k;
    for(int i=1;i<=k;i++)//输入 
    {
        cin>>s;
        while(s--)
        {
            m++;
            cin>>a[m];  
            if(m==a[m])vis[m]=1;
        }
    }
    for(int i=1;i<=m;i++)
        if(vis[i]==0)
        {
            int v=a[i];
            k=a[i];
            while(1)
            {
                vis[k]=1;//标记 
                k=a[k];//递归 
                ans++;//答案计数 
                if(k==0||vis[k]!=0)break; 
            }
            if(k==v)ans++;
        }
    if(ans!=0)cout<<"We need "<<ans<<" move operations."<<endl;//输出 
    else cout<<"No optimization needed."<<endl;
    return 0;
}