E Sequence in the Pocket

題源:http://acm.zju.edu.cn/onlinejudge/showContestProblem.do?problemId=5993

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.

[分析]

         開始的時候我是這麼想的：

         （1）開兩個數組 A[ ]   B[ ]   設定 ans=0

         （2）A[ ] 數組存儲單增的元素列   B[ ]數組存儲那些一定要拿到隊首進行改變的元素假設有 x 個 x 可以為0，ans+=x 

         （3）把B數組中的 bi 元素從大到小依次在A數組中找到 >= bi  的元素的位置 y,  ans+=y,  當 bi  <= A[0]時 則終止跳出 輸出                    ans

錯誤的代碼：

#include <iostream>
#include <queue>
#include <cstring>
#include <string>
#include <algorithm>
#include <cstdio>
using namespace std;
const int maxn=100005;
int n;
int t;
int a[maxn];
int b[maxn];
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        int f=0,cnt=0;
        int num=0;
        memset(a,0,sizeof 0);
        memset(b,0,sizeof 0);
        scanf("%d",&n);
        scanf("%d",&a[f]);f++;
        int x=0;
        for(int i=1;i<n;i++)
        {
            scanf("%d",&x);
            if(x>=a[f-1]) a[f++]=x;
            else b[cnt++]=x;
        }
        sort(b,b+cnt);
        num=cnt;
        if(cnt==0)
        {
            printf("0\n");
            continue;
        }
        if(b[cnt-1]<=a[0])
        {
            printf("%d\n",cnt);
            continue;
        }
        else
        {
                for(int i=cnt-1;i>=0;i--)
                num+=(lower_bound(a,a+f,b[i])-a);
                printf("%d\n",num);
        }
    }
    return 0;
}
           

  這個思路錯在并不是 B[ ] 數組中的所有元素都要重新在進行一遍 

num+=(lower_bound(a,a+f,b[i])-a);       

   操作。也就是說B[ ]數組中的最大值元素後面還可能會有其他的A[ ] 數組元素進行調到隊頭這一步操作，是以隻需要求B[ ] 中最大元素 num+=(lower_bound(a,a+f,b[cnt-1])-a); 就可以了。

#include <iostream>
#include <queue>
#include <cstring>
#include <string>
#include <algorithm>
#include <cstdio>
using namespace std;
const int maxn=100005;
int n;
int t;
int a[maxn];
int b[maxn];
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        int f=0,cnt=0;
        int num=0;
        memset(a,0,sizeof 0);
        memset(b,0,sizeof 0);
        scanf("%d",&n);
        scanf("%d",&a[f]);f++;
        int x=0;
        for(int i=1;i<n;i++)
        {
            scanf("%d",&x);
            if(x>=a[f-1]) a[f++]=x;
            else b[cnt++]=x;
        }
        sort(b,b+cnt);
        num=cnt;
        if(cnt==0)
        {
            printf("0\n");
            continue;
        }
        if(b[cnt-1]<=a[0])
        {
            printf("%d\n",cnt);
            continue;
        }
        else
        {

                num+=(lower_bound(a,a+f,b[cnt-1])-a);
                printf("%d\n",num);
        }
    }
    return 0;
}
           

 從這道題目中我覺得不應該輕易地放棄自己的原有思路，自己原有的思路并不一定全部都不對，可能隻是中間有一步沒有想完整，那我們就全盤否定轉别的思路可能就會耗更多的時間在心理上也對自己産生不小的壓力。