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; }