Cmi （HG 2018.10.1 T3）
hicc0305
2018-10-01 15:11:30
### 题目描述：
今有一全排列，每次可以移动一个数，求排序所需最少移动次数。
输入一个n，n个整数，是1~n的排列，n<=2e5
不多说，n-LIS，最长上升子序列nlogn二分优化
```
#include<ctime>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n,len=1;
int a[200100],b[200100];
int ans[200100];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
b[i]=n-a[i]+1;
ans[1]=a[1];
for(int i=2;i<=n;i++)
{
if(a[i]>ans[len]) {ans[++len]=a[i];continue;}
int j=lower_bound(ans+1,ans+len+1,a[i])-ans;
ans[j]=a[i];
}
printf("%d",n-len);
return 0;
}
```