poj 1033 文件移动-CSDN博客

本文链接：https://blog.csdn.net/dumeichen/article/details/50664152

本文探讨了在磁盘上高效地对多个文件进行优化排列的方法，以减少数据移动次数，提高磁盘读写效率。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

题意：磁盘n个块，有m个文件，各自被分割成许多块分散在磁盘之中，要求通过最少移动次数使得第1个文件的占1,2,3...f1块，第二个文件占f1+1,f1+2...f1+f2块。。。

思路：dfs（k）为将第k位置填好。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
using namespace std;
#define N 10005
int n,m;
int hh[N],s[N],len = 0,used[N];
int f;
int dfs(int i){
    used[i] = 1;
    if(!s[i]){
        printf("%d %d\n",hh[i],i);
        if(f == i)
            f = hh[i];
        s[hh[i]] = 0;
        s[i] = i;
        hh[i] = i;
        return false;
    }
    if(used[s[i]]){                 //遇到环
        printf("%d %d\n",i,f);
        hh[s[i]] = f;
        s[f] = s[i];
        s[i] = 0;
        f = i;
        return true;
    }else{
        int ans = dfs(s[i]);        //ans为真表示遇到环
        if(ans){                    //遇到环，那么当前的文件移动到他该去的地方
            printf("%d %d\n",i,s[i]);
            if(f==s[i])
                f = i;
            hh[s[i]] = s[i];
            s[s[i]] = s[i];
            s[i] = 0;
        }else{
            printf("%d %d\n",hh[i],i);  //如果不是环，那么是该放到当前位置的文件放过来（类似第一个分支）
            if(f == i)
                f = hh[i];
            s[hh[i]] = 0;
            s[i] = i;
            hh[i] = i;
        }
        return ans;
    }
}
int main(){
    int i,j,k,x;
    while(scanf("%d %d",&n,&k)!=EOF){
        memset(s, 0, sizeof(s));
        memset(hh, 0, sizeof(hh));
        len = 0;
        while(k--){
            scanf("%d",&j);
            for(i = 0;i<j;i++){
                scanf("%d",&x);
                hh[++len] = x;
                s[x] = len;
            }
        }
        for(i = n;i>=1;i--)//找一个空白的位置
            if(!s[i]){
                f = i;
                break;
            }
        for(i = 1;i<=len;i++)//看看是不是每个位置都放好了
            if(s[i] != i)
                break;
        if(i == len+1)
            printf("No optimization needed\n");
        else{
            for(int i = 1;i<=len;i++)
                if(s[i] != i){
                    memset(used, 0, sizeof(used));
                    if(dfs(i))
                        i--;
                }
        }
    }
    return 0;
}