AGC024 B Backfront

問題文

https://beta.atcoder.jp/contests/agc024/tasks/agc024_b

 

選ばない要素は公差1の等差数列になっていないといけない.

そうなっていれば,適当な順で先頭と末尾にうごかすことでソートできる.

例えば3 2 5 1 4 6の場合,3 4を固定して2を先頭に,1を先頭に,5を末尾に,6を末尾にうごかすことで4回で出来る.

という訳で一番長い等差数列を見つければよい.

 ソースコード

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const ll MOD = 1000000007LL;
int pos[200000];
int main() {
    int N;
    cin >> N;
    for (int i = 0; i < N; i++) {
        int P;
        cin >> P;
        pos[P - 1] = i;
    }
    int ans = 0;
    int len = 1;
    for (int i = 1; i < N; i++) {
        if (pos[i - 1] < pos[i]) len++;
        else ans = max(ans, len), len = 1;
    }
    ans = max(ans, len);
    cout << N - ans << endl;
}