東京工業大学プログラミングコンテスト2015 I - そーっとソート
これほんと感動しました。
解法
右端から揃えていく感じでやります。
例えば, 4, 2, 5, 3, 1 という順列があったとします。右端は 5 にしたいですが, 5 になっていないので右端の 1 を動かします。ルールにより, 1 の場所から 1 だけずれてる 3 と交換します。
4 2 5 3 1 -> 4 2 5 1 3
右端は 3 になりましたが, これも目的と違います。ということで, 動かします。さらに動かします。
4 2 5 1 3 -> 4 3 5 1 2 -> 4 3 2 1 5
ここで, 右端が 5 になってくれました。嬉しいです。これを 4, 3, 2, 1 とやっていけば良いです。
このようなアルゴリズムでは, N を右端に揃えたい場合, たかだか N 回の操作で N が右端に来ることが保証されるので, 十分指定された回数以内に間に合います。
const int MAXN = 55; int A[MAXN]; int main() { cin.tie(0); ios::sync_with_stdio(false); int N; cin >> N; for (int i = 0; i < N; i++) cin >> A[i]; vector<pii> ps; int cur = N-1; while (cur >= 0) { while (A[cur] != cur+1) { ps.emplace_back(cur, cur-A[cur]); swap(A[cur], A[cur-A[cur]]); } cur--; } cout << ps.size() << endl; for (auto p : ps) { cout << p.first+1 << " " << p.second+1 << endl; } return 0; }