AK-dream

【题目描述】
一个数组的元素为 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)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#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;
}

 评论