CS Academy To Front - To Back

リンク : https://csacademy.com/contest/archive/task/to-front-to-back/statement/

問題概要

長さNの1～Nを一つずつ含む数列が与えられる。この数列をソートしたい。任意の数字を先頭か後尾に移動させることによってソートする。ソートし終わったときのこの操作の最小回数とその操作の内容を出力せよ。

解説

まず、数字iのindexをindex[i]とおく。index[i]<index[i+1] である連続の整数の最長の長さを求める。この最長に含まれる数字は、移動させずにほかを移動させることで最小の回数になる。l～rがその範囲であるとすると、l-1,l-2...1までを順番に先頭に移動させてから、r+1,r+2...nを後尾に持っていくことで最小の回数となる。

LL n, dp[110000];
Pll a[110000], mx;
int main() {
    cin >> n;
    rep(i, n) {
        cin >> a[i].fir;
        a[i].sec = i;
    }
    sort(a, a + n);
    rep(i, n - 1) {
        if (a[i].sec < a[i + 1].sec) {
            dp[i + 1] = dp[i] + 1;
            if (dp[i + 1] > mx.fir) {
                mx.fir = dp[i + 1];
                mx.sec = i + 2;
            }
        }
    }
    cout << n - mx.sec + mx.sec - mx.fir - 1 << endl;
    for (int i = mx.sec + 1; i <= n; i++)
        cout << i << " " << 1 << endl;
    for (int i = mx.sec - mx.fir - 1; i > 0; i--)
        cout << i << " " << 0 << endl;
    return 0;
}