CIM

Description

给出一个1到n的排列，每次可以移动一个数到一个任意位置。问要达到状态1,2,3……n至少移动多少次？

Input

n　（１<=n<=100000）
n个数

Output

移动次数！

Sample Input

5
2 1 4 5 3

Sample Output

2

解题思路

这道题其实就是求n-最长上升子序列的长度。动态转移方程：
i f ( a [ i ] > = f [ m ] ) m + + ; f [ m ] = a [ i ] ; if(a[i]>=f[m]){m++;f[m]=a[i];} if(a[i]>=f[m])m++;f[m]=a[i];
e l s e else else
i n t int int j = u p p e r b o u n d ( f + 1 , f + m + 1 , a [ i ] ) − f ; f [ j ] = a [ i ] ; j=upper_bound(f+1,f+m+1,a[i])-f;f[j]=a[i]; j=upperb​ound(f+1,f+m+1,a[i])−f;f[j]=a[i];

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m=1,a[100001],f[100001],maxn;
int main()
{
   
    cin>>n;
    for(int i=1;i<=n;i++)
	 cin>>a[i];
    f[1]=a[1];
    for(int i=2;i<=n;i++)
    {
   
        if(a[i]>=f[m]){
   m++;f[m]=a[i];}
        else{
   int j=upper_bound(f+1,f+m+1,a[i])-f;f[j]=a[i];}
        maxn=max(m,maxn);
    }
    cout<<n-maxn;
    return 0;
}

谢谢阅读，如有疑惑或发现作者错误可在评论区留言