Codeforces 606-C：Sorting Railway Cars（LIS）-白红宇

Codeforces 606-C：Sorting Railway Cars（LIS）

阅读量：6987 次

发布时间：2019-06-27

本文共 2151 字，大约阅读时间需要 7 分钟。

An infinitely long railway has a train consisting of n cars, numbered from 1 to n (the numbers of all the cars are distinct) and positioned in arbitrary order. David Blaine wants to sort the railway cars in the order of increasing numbers. In one move he can make one of the cars disappear from its place and teleport it either to the beginning of the train, or to the end of the train, at his desire. What is the minimum number of actions David Blaine needs to perform in order to sort the train?

Input

The first line of the input contains integer n (1 ≤ n ≤ 100 000) — the number of cars in the train.

The second line contains n integers pi (1 ≤ pi ≤ n, pi ≠ pj if i ≠ j) — the sequence of the numbers of the cars in the train.

Output

Print a single integer — the minimum number of actions needed to sort the railway cars.

      Examples 
        input 
         Copy 
54 1 2 5 3
        output 
         Copy 
2
        input 
         Copy 
44 1 3 2
        output 
         Copy 
2

Note

In the first sample you need first to teleport the 4-th car, and then the 5-th car to the end of the train.

这是分割线

题意：有n辆车，每辆车编号从1—n，但是顺序是无序的，有两种操作：1.将车移到最前面。2.将车移到最后面。问最少需要几次操作能让这些车的编号从小到大排序

思路：求出这些无序的编号中最长的上升子序列长度L（注意这个序列中相邻的元素相差为1），然后用n减去L就可以了（具体不知道为什么，但是随便找几组数据推一下就能出来）

实现：开两个数组a，b，a储存无序的车序号，b储存从开头到序号a[i]的上升子序列。

如第一组样例：4 1 2 5 3

a[1]=4，在4之前没有比4小1的数，所以b[a[1]]=1，即：b[4]=1；

同理b[1]=1

a[3]=2，因为能找到比2小1的数，且b[a[3]-1]=b[1]=1，即：b[2]=b[1]+1=2；

同理b[5]=b[4]+1=2；

b[3]=b[2]+1=3；

然后找出b数组中的最大值ans，n-ans即可得到正确结果

LIS的时间复杂度为O（n）

AC代码：

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          #include 
           
            #include 
            
             #include 
             
              #define ll long long#define INF 0x3f3f3f3fconst int maxn=1e6+10;int a[maxn];int b[maxn];int main(int argc, char const *argv[]){ int n; scanf("%d",&n); memset(b,0,sizeof(b)); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); b[a[i]]=b[a[i]-1]+1; } int ans=1; for(int i=1;i<=n;i++) { ans=std::max(ans,b[a[i]]); } printf("%d\n",n-ans); return 0;}

转载于:https://www.cnblogs.com/Friends-A/p/9308984.html

你可能感兴趣的文章