codeforces C. Sorting Railway Cars 贪心

梦里梦外; 2022-08-18 15:22 2阅读 0赞

C. Sorting Railway Cars

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

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 *p**i* (1 ≤ *p**i* ≤ *n*, *p**i* ≠ *p**j* 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.

Sample test(s)

Input

5
    4 1 2 5 3

Output

Input

4
    4 1 3 2

Output

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.

题意: 有一个1-n的排列(排列是指全是1-n中的数字,并且各不相同), 每次可以任意从里面拿出来一个放在最前面或者最后面,求最小的次数把这个数列排好序.

分析: 开始想的是求这个排列中的最长递增子序列, 找到最长的一部分, 这一部分不用动, 只动别的部分就行, 然而是不对的, 比如1 2 4 5 3就不符合, 后来一想, 最长递增子序列的相邻两个必须是差值为一. 这样才能保持不动, 然后动别的数..

#include<bitset>
    #include<map>
    #include<vector>
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<cmath>
    #include<stack>
    #include<queue>
    #include<set>
    #define inf 0x3f3f3f3f
    #define mem(a,x) memset(a,x,sizeof(a))
    
    using namespace std;
    
    typedef long long ll;
    typedef pair<int,int> pii;
    
    inline int in()
    {
        int res=0;char c;
        while((c=getchar())<'0' || c>'9');
        while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
        return res;
    }
    const int N=100100;
    
    int a[N],sum[N],ans;
    int main()
    {
        int n=in();
        for(int i=0;i<n;i++)
        {
            int x=in();
            sum[x]=sum[x-1]+1;   //这个数的差值为1的最长递增子序列等于前面一个数的最长递增子序列加1
            ans=max(ans,sum[x]);
        }
        cout<<n-ans<<endl;
        return 0;
    }

类似题: hdu 5500

# Reorder the Books #

**Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)  
Total Submission(s): 994    Accepted Submission(s): 554**

Problem Description

dxy has a collection of a series of books called "The Stories of SDOI",There are  *n*(*n*≤19) books in this series.Every book has a number from  1 to  *n*.  
  
dxy puts these books in a book stack with the order of their numbers increasing from top to bottom. dxy takes great care of these books and no one is allowed to touch them.  
  
One day Evensgn visited dxy's home, because dxy was dating with his girlfriend, dxy let Evensgn stay at home himself. Evensgn was curious about this series of books.So he took a look at them. He found out there was a story about "Little E&Little Q". While losing himself in the story,he disrupted the order of the books.  
  
Knowing that dxy would be back soon,Evensgn needed to get the books ordered again.But because the books were too heavy.The only thing Evensgn could do was to take out a book from the book stack and and put it at the stack top.  
  
Give you the order of the disordered books.Could you calculate the minimum steps Evensgn would use to reorder the books? If you could solve the problem for him,he will give you a signed book "The Stories of SDOI 9: The Story of Little E" as a gift.

Input

There are several testcases.  
  
There is an positive integer  *T*(*T*≤30) in the first line standing for the number of testcases.  
  
For each testcase, there is an positive integer  *n* in the first line standing for the number of books in this series.  
  
Followed  *n* positive integers separated by space standing for the order of the disordered books,the  *i**t**h* integer stands for the  *i**t**h* book's number(from top to bottom).  
  
  
**Hint:**  
For the first testcase:Moving in the order of  *b**o**o**k*3,*b**o**o**k*2,*b**o**o**k*1 ,  (4,1,2,3)→(3,4,1,2)→(2,3,4,1)→(1,2,3,4),and this is the best way to reorder the books.  
For the second testcase:It's already ordered so there is no operation needed.

Output

For each testcase,output one line for an integer standing for the minimum steps Evensgn would use to reorder the books.

Sample Input

2
    4
    4 1 2 3
    5
    1 2 3 4 5

Sample Output

3
    0

Source

[BestCoder Round \#59 (div.1) ][BestCoder Round _59 _div.1_]

题意: 1-n的排列, 每次从中选择一个数放在最前面, 求最小的步数使得数列排好序.

分析: 这次是只能放在最前面. ,想一下应该固定的最长的序列应该是什么样的,  这次就不是上面的差值为1的最长递增子序列了, 而是结尾为n的差值为1的最长递增子序列.因为如果结尾不是n的话,这段数列是不能固定的, 因为结尾不是n的话,肯定有比他们大的数在他们前面, 这段肯定会被移动.

拓展: 1-n的排列, 每次从中选择一个数放在最后面, 求最小的步数使得数列排好序.?

#include<bitset>
    #include<map>
    #include<vector>
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<cmath>
    #include<stack>
    #include<queue>
    #include<set>
    #define inf 0x3f3f3f3f
    #define mem(a,x) memset(a,x,sizeof(a))
    
    using namespace std;
    
    typedef long long ll;
    typedef pair<int,int> pii;
    
    inline int in()
    {
        int res=0;char c;
        while((c=getchar())<'0' || c>'9');
        while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
        return res;
    }
    const int N=100100;
    int sum[N];
    
    int main()
    {
        int T=in();
        while(T--)
        {
            int n=in();
            mem(sum,0);
            for(int i=0;i<n;i++)
            {
                int x=in();
                sum[x]=sum[x-1]+1;
            }
            cout<<n-sum[n]<<endl; //n-结尾为n的差值为1的最长递增子序列
    
        }
        return 0;
    }

官方题解: 首先发现最大的数n是不用操作的, 操作的话只会让步数增加, 操作别的数到他前面去, 他自然就在后面了,我们从后往前找到n的位置, 从n的位置往前找到n-1的位置,如果没找到, 说明n-1在n的后面, 那么原数列肯定最少需要n-1次操作排序 ,(把n-1移到最前面, 然后从大到小一个个移动就行了,); 如果n-1在n 的前面, 那么n-1就不用移动了, 原理同n的一样,同理， 我们接着从(n−1)(n-1的位置往前找(n−2)(n-2),再从(n−2)(n-2)的位置往前找(n−3)(n-3)...假如数kk找不到了，那么就至少需要kk次操作。这种做法的复杂度是O(n)O(n)的

#include<bitset>
    #include<map>
    #include<vector>
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<cmath>
    #include<stack>
    #include<queue>
    #include<set>
    #define inf 0x3f3f3f3f
    #define mem(a,x) memset(a,x,sizeof(a))
    
    using namespace std;
    
    typedef long long ll;
    typedef pair<int,int> pii;
    
    inline int in()
    {
        int res=0;char c;
        while((c=getchar())<'0' || c>'9');
        while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
        return res;
    }
    const int N=100010;
    
    int a[22];
    int main()
    {
        int T=in();
        while(T--)
        {
            int n=in();
            for(int i=0;i<n;i++) a[i]=in();
            int ans=n;
            for(int i=n-1;i>=0;i--)
            {
                if(ans==a[i]) ans--;
            }
            cout<<ans<<endl;
        }
        return 0;
    }

[BestCoder Round _59 _div.1_]: http://acm.hdu.edu.cn/search.php?field=problem&key=BestCoder+Round+%2359+%28div.1%29&source=1&searchmode=source