0w1

IOI 15 Sorting ( Binary Search + Greedy )

PEG Judge - IOI '15 - Sorting
首先我們要想到,如果 k回合內能完成,那麼 k + 1回合內一定也能完成,這是很顯然的,因為對方換了什麼,換回來就行了。所以我們可以進行二分搜,現在問題就簡化成要在O( n ) 判斷 k回合內可不可能達成。
接著要發現,設原始序列為 a,只經過對方的 k個操作操作後成為序列 b,那麼如果希望某個 b[ i ]和 b[ j ]對調,顯然只要在對方第一次操作結束的時候將 b[ i ]和 b[ j ]兩個數字對調即可。注意到是不能在任意時刻換的,這部分需要小心。接著,想想看要怎麼把最終序列用最少的操作數排序。這裡不附證明,由左到右,依次將每個位置裡該有的東西 swap過來,一定會是最少的。
結論是,分別維護當前序列最終序列,和他們的反查函數( 查找某個數字在序列中第幾個位置 ),利用前述的方法依序將最終序列排好,一方面維護當前序列紀錄答案就行了。
註:這種反來反去的東西真的很容易出問題,除錯了半天。。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 5;
const int MAXM = 3 * MAXN;
typedef pair< int, int > pii;

int n;
int s[ MAXN ];
int m;
int opx[ MAXM ], opy[ MAXM ];

int c[ MAXN ];
int t[ MAXN ];
int pc[ MAXN ];
int pt[ MAXN ];
bool ok(int rnd, bool show){
    memcpy( t, s, sizeof(t) );
    memcpy( c, s, sizeof(c) );
    for(int i = 0; i < rnd; ++i)
        swap( t[ opx[ i ] ], t[ opy[ i ] ] );
    for(int i = 0; i < n; ++i)
        pt[ t[ i ] ] = i;
    for(int i = 0; i < n; ++i)
        pc[ c[ i ] ] = i;
    if( show ) printf("%d\n", rnd);
    vector< pii > ans;
    int cnt = 0;
    int z = 0;
    for(int i = 0; i < rnd; ++i){
        swap( c[ opx[ i ] ], c[ opy[ i ] ] );
        swap( pc[ c[ opx[ i ] ] ], pc[ c[ opy[ i ] ] ] );
        // for(int i = 0; i < n; ++i) printf("%d ", c[ i ]); puts("");
        while( z < n && t[ z ] == z ) ++z;
        if( z == n ) break;
        int u = z, v = t[ z ];
        // for(int i = 0; i < n; ++i) printf("%d ", t[ i ]); puts("");
        swap( pt[ u ], pt[ v ] );
        swap( t[ pt[ u ] ], t[ pt[ v ] ] );
        swap( pc[ u ], pc[ v ] );
        swap( c[ pc[ u ] ], c[ pc[ v ] ] );
        // printf("%d %d\n", u, v);
        ans.push_back( pii( pc[ u ], pc[ v ] ) );
        ++z;
        ++cnt;
        // for(int i = 0; i < n; ++i) printf("%d ", c[ i ]); puts("");
        // for(int i = 0; i < n; ++i) printf("%d ", t[ i ]); puts("");
    }
    while( z < n && t[ z ] == z ) ++z;
    if( z < n ) return false;
    if( show ){
        for(int i = 0; i < ans.size(); ++i)
            printf("%d %d\n", ans[ i ].first, ans[ i ].second);
        while( cnt++ < rnd ) puts("0 0");
    }
    return true;
}

void solve(){
    int ans = -1;
    int lb = 0, ub = m;
    while( lb <= ub ){
        int mid = lb + ub >> 1;
        if( ok( mid, false ) ) ans = mid, ub = mid - 1;
        else lb = mid + 1;
    }
    ok( ans, true );
}

int main(){
    scanf("%d", &n);
    for(int i = 0; i < n; ++i)
        scanf("%d", &s[ i ]);
    scanf("%d", &m);
    for(int i = 0; i < m; ++i)
        scanf("%d%d", &opx[ i ], &opy[ i ]);
    solve();
    return 0;
}