C. Omkar and Baseball (Codeforces Round #655 Div. 2)

問題

https://codeforces.com/contest/1372/problem/C

問題概要

長さnの順列が与えられる。この順列を昇順にソートしたい。以下の条件で並べ替えを実行する時、最小の並べ替え回数は何回か？

• 連続した部分配列を指定する
• 指定された部分配列の中で要素を入れ替える
  • ただし、すべての要素を確かに入れ替えなければならない（同じ位置にとどまる要素があってはならない）

考察

実は最悪ケースでも2回の並べ替えで昇順に並ぶことは容易にわかります。1回目の並べ替えでいったんすべての要素を適当に不適切な位置に置けば、2回目の並べ替えですべてを昇順に並べることが可能だからです。

そこで、0または1回で済むケースを考えてみます。

0回となるのはいうまでもなく最初からソート済みである場合のみです。

1回で済むのは、ソートされていない要素だけで構成される部分列が1組のみ存在する場合です。この場合、その部分列を1度並べ替えすればすべてがソート済みになります。

もし、そのような部分列が別の場所に2つ以上存在した場合、別々に並べ替えすれば2回以上かかってしまいますし、まとめて並べ替えしようとするとそれらの部分列の間に含まれるソート済みの要素を巻き込んでしまい、同じ位置にあってはならないという条件からすべてをソート済みの状態にすることが不可能だからです。

例えば1 3 2 4 6 5として、ソート済みでない区間は3 2と6 5ですが、それらを別々に並べ替えすると2回かかり、一度に並べ替えしようとするとすでに適切な位置にある4を一旦動かさなくてはならなくなり、戻すためにもう一度操作する必要が出てしまうためです。

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        int different_range_count = 0;
        bool different_range = false;
        bool all_ok = true;
        int a;
        for (int i = 1; i <= n; i++) {
            cin >> a;
            if(i != a) {
                all_ok = false;
                if (!different_range) {
                    different_range_count++;
                    different_range = true;
                }
            } else {
                if (different_range) {
                    different_range = false;
                }
            }
        }
        if (all_ok) cout << 0 << endl;
        else cout << min(2, different_range_count) << endl;
    }
}