CF605A Sorting Railway Cars

传送门

题目大意

给出一个 1 到 n 的排列，每次操作可以将某个位置的数字移动到最前面或最后面，求将排列从小到大排序的最小操作次数

如：4 1 2 5 3 操作1：将5和3换一下变成4 1 2 3 5

操作2：将1 2 3和 4换一下变成 1 2 3 4 5 在此后即完成要求。所以最小操作次数为2。

输入：

第一行 为长度 nnn ; 第二行为原来的顺序两个数之间有空格。

输出：

最小操作次数

解题思路

因为要从小到大排序，所以我们很自然能想到lis，但是也很容易举出反例。如1 2 4 5 3，如果求lis的话答案为1，实际上答案应该是2。是因为只能将数字移动到末尾或开头。但如果是连续的数字就可以不用进行操作，所以这道题应该是求出一段连续的lis，比如上面那个数据求出的话应该是3 1 2 3 。因为数字保证是一个n的排列，所以这比直接求lis要简单，直接开个桶记录上一个有没有出现，直接进行转移即可。

代码

#include<iostream>

#include<cstdio>

using namespace std;

const int MAXN = 100005;

inline int rd(){

    int x=0,f=1;char ch=getchar();

    while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}

    while(isdigit(ch))  {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}

    return x*f;

}

int n,a[MAXN];

int dp[MAXN],ans;

bool vis[MAXN];

int main(){

    n=rd();

    for(register int i=1;i<=n;i++){

        a[i]=rd();

        vis[a[i]]=1;

        if(vis[a[i]-1]) dp[a[i]]=dp[a[i]-1]+1;

        else dp[a[i]]=1;

        ans=max(ans,dp[a[i]]);

    }

    printf("%d",n-ans);

    return 0;

}