CodeForces 606C
车辆排序
CodeForces 606C
Description
一个无限长的铁路有一个载着n辆车的火车，每一辆车的编号从1到n。每一辆车的编号都是不同的。他们的顺序是无序的。
David Blaine想要将这些车按照他们的编号从小到大排序，他可以做两种操作。第一种，他可以将一辆车从任意位置移动到所有车的第一位。第二种，他可以将一辆车从任意位置移动到所有车的最后一位。
不过他很懒，所以他想知道将这些车排好序最少做几次操作就可以。
Input
第一行输入包含一个整数n (1 ≤ n ≤ 100 000) -- 车的数目
第二行包含n个整数 pi (1 ≤ pi ≤ n, pi ≠ pj if i ≠ j) - 车的编号的初始序列
Output
输出一个整数 - 将车辆排好序的最小操作次数
Sample Input
5
4 1 2 5 3
4
4 1 3 2
Sample Output
2
2
Hint
在第一个样例中，将编号为4的车放到最后，然后把编号为5的车放到最后就可以了。总共是2次操作。
题意：
给出一个序列, 任一个数可以放到序列末尾或者最前, 输出最小操作数
思路：
求最长连续上升长度ans，n-ans即为答案
#include <stdio.h>
#include <string.h>
int jl[100005];
int main()
{
int n, ans, k;
while(~scanf("%d", &n))
{
ans = 0;
memset(jl, 0, sizeof jl);
for(int i = 1; i <= n; ++i)
{
scanf("%d", &k);
if(jl[k-1])
{
jl[k] = jl[k-1]+1;
}
else jl[k] = 1;
ans = ans < jl[k]? jl[k]: ans;
}
printf("%d\n", n-ans);
}
return 0;
}