PKU 1033 Defragment - kusano

各ファイルを移動すべきクラスタは一意に定まる。そのようなクラスタが空いていればファイルを移動、空きがなければ位置が間違っているファイルを適当なクラスタに移動、が最善。O(n²)で間に合うようだ。

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int N, K;  cin >> N >> K;

    vector<int> C1( N+1, -1 );      //  クラスタ
    vector<int> C2( N+1, -1 );      //  i番目のデータの現在の位置

    int M = 0;  //  総クラスタ数
    for ( int i=0; i<K; i++ )
    {
        int n;  cin >> n;
        for ( int j=0; j<n; j++ )
        {
            int t;  cin >> t;
            M++;
            C1[t] = M;
            C2[M] = t;
        }
    }

    int m = 0;  //  移動回数

    while ( true )
    {
        bool f = false;

        //  空きクラスタにデータを移動
        for ( int i=1; i<=M && !f; i++ )
            if ( C1[i] == -1 )
            {
                cout << C2[i] << " " << i << endl;
                C1[i] = i;
                C1[C2[i]] = -1;
                C2[i] = i;
                m++;
                f = true;
            }

        //  位置が間違っているデータを後ろの空きクラスタに
        for ( int i=1; i<=M && !f; i++ )
            if ( C1[i] != i )
            {
                cout << i << " " << N << endl;
                C1[N] = C1[i];
                C2[C1[i]] = N;
                C1[i] = -1;
                m++;
                f = true;
            }

        if ( ! f )
            break;
    }

    if ( m == 0 )
        cout << "No optimization needed" << endl;
}