ZOJ - 4104 Sequence in the Pocket（思维+元素移至列首排序）

àì夳堔傛蜴生んèń 2021-11-11 02:00 150阅读 0赞

**Sequence in the Pocket**

--------------------

Time Limit: 1 Second       Memory Limit: 65536 KB

--------------------

DreamGrid has just found an integer sequence  in his right pocket. As DreamGrid is bored, he decides to play with the sequence. He can perform the following operation any number of times (including zero time): select an element and move it to the beginning of the sequence.

What's the minimum number of operations needed to make the sequence non-decreasing?

#### Input ####

There are multiple test cases. The first line of the input contains an integer , indicating the number of test cases. For each test case:

The first line contains an integer  (), indicating the length of the sequence.

The second line contains  integers  (), indicating the given sequence.

It's guaranteed that the sum of  of all test cases will not exceed .

#### Output ####

For each test case output one line containing one integer, indicating the answer.

#### Sample Input ####

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

#### Sample Output ####

2
    0

#### Hint ####

For the first sample test case, move the 3rd element to the front (so the sequence become \{2, 1, 3, 4\}), then move the 2nd element to the front (so the sequence become \{1, 2, 3, 4\}). Now the sequence is non-decreasing.

For the second sample test case, as the sequence is already sorted, no operation is needed.

题意：给定一个序列，每次可以把一个元素移到列首（最左边），求最少移几次使其有序（非降序）

（之前做过类似的题，可以把元素移到首或尾，思路相似）

思路：因为左移，可以肯定移动的都是较小值，若要保证操作次数最少，最大值一定不需要移动。

所以先排好序，确定之间的相对大小，然后找到最大值位置（因为有相同元素so从右往左找）

再从最大值往左找次大值，因为除最大值外，次大值就是当前最大值，所以同样不需要移动。

以此类推，直到找到最左边结束，我们找到的值都是不需要移动的，那么用总个数n减不需移动的个数ans即为需要移动的个数，解保证最小。

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    
    int a[100005],b[100005];
    
    int main()
    {
        int t,n,i,j;
        scanf("%d",&t);
        while(t--){
            scanf("%d",&n);
            int ma=0;
            for(i=1;i<=n;i++){
                scanf("%d",&a[i]);
                b[i]=a[i];
            }
            sort(b+1,b+n+1);
            int ans=0;
            for(i=n;i>=1;i--){
                if(a[i]==b[n]){
                    int c=n;
                    for(j=i;j>=1;j--){
                        if(a[j]==b[c]){
                            c--;
                            ans++;
                        }
                    }
                    break;
                }
            }
            printf("%d\n",n-ans);
        }
        return 0;
    }

转载于:https://www.cnblogs.com/yzm10/p/10887303.html