Description
给出一个1到n的排列，每次可以移动一个数到任意一个位置（第一个数前，最后一个数后或者两个数之间的位置）。问要达到状态1; 2; 3⋯⋯n至少移动多少次？
Input
第一行一个正整数N。
第二行N个整数，表示一个1到n的排列。
Output
在第一行输出最少的移动次数。
Sample Input
5
2 1 4 5 3
Sample Output
2Data Constraint
Hint
数据范围
在50%的数据中，1<=N<=5000
在100%的数据中，1<=N<=200000
Solution
因为每个数可以移动到任意位置，首先对于一个序列最多移动n-1次，我们考虑在什们情况下要移动n-1次，显然是这个序列从n到1排列时。
最先想到如果我希望用最小的移动次数是这个序列有序，那么肯定是移动那些不在相对位置上的那些数，
再想想，
意思就是，
保留那些相对位置递增的数。
那么我们要求的就是最多的递增的数。
那不就是最长不下降子序列吗？
最后得出结论，答案=n-最长不下降子序列的长度。
Code
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define I int
#define N 200010
#define F(i,a,b) for(I i=a;i<=b;i++)
#define Fd(i,a,b) for(I i=a;i>=b;i--)
#define open(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout);
using namespace std;
I rd(){I x=0;char ch=getchar();while(ch<'0'||ch>'9') ch=getchar();while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x;
}
I n,f[N],len,l,r,mid,k,a[N];
I main(){open("CMI");n=rd();F(i,1,n) a[i]=rd();f[len=1]=a[1];F(i,2,n){if(a[i]>f[len]) f[++len]=a[i];else{l=1,r=len,k=0;while(l<=r){mid=(l+r)>>1;if(f[mid]<a[i]) l=mid+1;else{k=mid;r=mid-1;}}f[k]=a[i];}}printf("%d\n",n-len);return 0;
}作者：zsjzliziyang
QQ:1634151125
转载及修改请注明
本文地址:https://blog.csdn.net/zsjzliziyang/article/details/99610930
