特殊的排列「NOIP多校联考 2019」

【题目描述】
一个数组的元素为 1 至 N 的整数，现在要对这个数组进行排序，在排序时只能将元素放在数组的头部或尾部，问至少需要移动多少个数字，才能完成整个排序过程？
2 5 3 4 1 将 1 移到头部 ?
1 2 5 3 4 将 5 移到尾部 ?
1 2 3 4 5 这样就排好了，移动了 2 个元素。
给出一个 1-N 的排列，输出完成排序所需的最少移动次数。

【输入格式】
第 1 行：1 个数 \(N(2\leq N\leq 50000)\)。
第 2 ~ N+1 行：每行 1 个数，对应排列中的元素。

【输出格式】
输出 1 个数，对应所需的最少移动次数。

考试的时候 把结论猜对了 不然我估计我也推不出这个结论来QWQ

结论是这样的
假设你以最少的移动次数排好了序 那么你一定会将1~p的这些数按照p, p-1, p-2, ..., 2, 1的顺序依次挪到最前面 将q~n的数按q, q+1, q+2, ..., n - 1, n的顺序挪到最后面
这样移动的所需次数一定是最少的
那么还有一部分数 p+1~q-1 是不需要移动的 为了让移动次数最少 我们肯定想要这段 p+1~q-1 最长
这段数字还必须是连续的正整数 所以问题就变成了求序列中最长的 由连续正整数构成的 子序列
这个其实也很容易求 设\(ind[i]\)表示 数字\(i\)在序列中的位置 以上文样例为例 \(ind\)数组应该是这样的：\(\{5, 1, 3, 4, 2\}\) 然后其实就是求这个数组的最长连续上升子序列 遍历一遍就行了 时间复杂度\(O(n)\)

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;

ll read() {
    ll ret = 0, flag = 1;
    char ch = getchar();
    while (ch > '9' || ch < '0') {
        if (ch == '-') flag = -1;
        ch = getchar();
    }
    while (ch <= '9' && ch >= '0') {
        ret = (ret << 3) + (ret << 1) + (ch ^ '0');
        ch = getchar();
    }
    return ret * flag;
}

ll n, a[100005], b[100005];
ll maxn, maxst;

int main() {
    n = read();
    for (int i = 1; i <= n; i++) {
        a[i] = read();
        b[a[i]] = i;
    }
    ll st = 1; 
    for (int i = 2; i <= n; i++) {
        if (b[i] < b[i-1]) {
            if (i - st > maxn) {
                maxn = i - st;
            }
            st = i;
        } 
    }
    if (n - st + 1 > maxn) maxn = n - st + 1; 
    printf("%lld\n", n - maxn);
    return 0;   
}

特殊的排列「NOIP多校联考 2019」

原文：https://www.cnblogs.com/ak-dream/p/AK_DREAM15.html