其实就是求总长度 - 一个最长“连续”自序列的长度

最长“连续”自序列即一个最长的lis，并且这个lis的值刚好是连续的，比如4，5，6...

遍历一遍，贪心就是了

遍历到第i个时，此时值为a[i],如果a[i]-1在前面已经出现过了，则len[a[i]] = len[a[i-1]]+1

否则len[a[i]] = 1

 

 

#include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;const int MAXN = 100000+10;bool pos[MAXN];int len[MAXN];void solve(){    int n;    scanf("%d",&n);    memset(pos,false,sizeof pos);    for(int i=1;i<=n;i++){        int a;        scanf("%d",&a);        if(pos[a - 1]){            len[a] = len[a-1] + 1;        }        else{            len[a] = 1;        }        pos[a] = true;    }    int ma = -1;    for(int i=1;i<=n;i++){        if(len[i] > ma)            ma = len[i];    }    printf("%d\n",n - ma);    return ;}int main(){    solve();    return 0;}