HDU 5500 Reorder the Books

亦凉 2022-08-09 05:10 16阅读 0赞

题目链接：[http://acm.hdu.edu.cn/showproblem.php?pid=5500][http_acm.hdu.edu.cn_showproblem.php_pid_5500]

题目大意：有一堆编号混序的书，每次可以把一本书放在最上面，问最少几移动次可以把书变为有序的。

题解：  
假设有一堆序列号最大为8的书。  
判断8前面是否有7，如果没有，那么肯定要将7移动到最前面，如果7在最前面，那么肯定要移动654321这几本书，结果为7。  
如果8前面有7，那么再判断7前面是否有6，如果没有那么肯定要将6移动到最前面，如果6再最前面，肯定要再移动54321这几本书，结果为6。  
也就是说8前面如果有7，那么可以少移动一次，7前面如果有6，又可以少移动一次  
依此类推即可。

代码：

#include <set>
    #include <list>
    #include <stack>
    #include <queue>
    #include <deque>
    #include <cmath>
    #include <ctime>
    #include <cstdio>
    #include <vector>
    #include <bitset>
    #include <sstream>
    #include <cstdlib>
    #include <climits>
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    #define RI(N) scanf("%d",&(N))
    #define RII(N,M) scanf("%d %d",&(N),&(M))
    #define RIII(N,M,K) scanf("%d %d %d",&(N),&(M),&(K))
    #define Cl0(a) memset((a),0,sizeof(a))
    using namespace std;
    const int inf=1e9;
    const int inf1=-1*1e9;
    typedef long long LL;
    int main()
    {
        int cas;
        scanf("%d",&cas);
        while(cas--)
        {
            int n,a[25];
            RI(n);
            //cout<<n<<endl;
            for(int i=0;i<n;i++)
            {
                RI(a[i+1]);
            }
            for(int i=n;i>=1;i--)
            {
                if(a[i]==n)   n--;     
            }
            printf("%d\n",n);
        }
        return  0;
    }

[http_acm.hdu.edu.cn_showproblem.php_pid_5500]: http://acm.hdu.edu.cn/showproblem.php?pid=5500