CF605A

· · 题解

题目传送门

题目要用最少的操作次数使得数据为单调上升序列（我们使不进行移动的数字数量最大化）。

怎么让移动的次数最少呢？

我们用一个极端的样例试一试：

输入    输出
5       4
5
4
3
2
1

简述一下移动过程：

5\space4\space3\space2\space 1 \Rightarrow 5\space4\space3\space1\space 2 \Rightarrow5\space4\space1\space2\space 3 \Rightarrow 5\space1\space2\space3\space 4 \Rightarrow1\space2\space3\space4\space 5

4 次。

所以，最多的移动次数为 n-1 次！

但是有一些特殊的，例如下面的：1 8 4 2 7 3

1\space8\space4\space2\space7\space3 \Rightarrow 1\space8\space2\space7\space3\space4\Rightarrow1\space8\space2\space3\space4\space7\Rightarrow1\space2\space3\space4\space7\space8

3 次？！

为什么呢？1 2 3 可以永远不动，只需要 4 7 8 挨个往后移！

所以，次数为：n 减挨个上升的“子序列”的长度！

代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
    int a,b[200001]={0},i,m=-1,k=0,x;scanf("%d",&a);//定义变量。
   /*
   为什么要 b[200001]={0}？因为：第 8 句涉及到 b[0]。
   m=-1 是保险起见。
   */
    for(i=1;i<=a;i++){
        cin>>x;
        b[x]=b[x-1]+1;//关键，求“最长上升子序列”。
        m=max(m,b[x]);//更新。
    }
    cout<<a-m;
}

重题 AT_agc024_b~~