HDU 5500 Reorder the Books

題目

https://vjudge.net/problem/HDU-5500

題意是說給你一個打亂順序的區間，要求變成從小到大排列。每次移動一個數的時候都要把這個數放到區間的最前面，問最少的變成目标區間的操作次數。

題解

http://blog.csdn.net/Loi_black/article/details/78441083

原題的資料範圍很水，可以做到O(N*T)

考慮最糟糕的情況，我們固定最大的元素不動，把其他所有元素按照一定順序向上丢，這樣一定能得到答案。

如果有一個比最大數小的次大數在最大數的上方，顯然這個次大數是不必被丢的，ans-1

，同理，次大和次次大也是這樣

【困成狗，看black學長部落格吧】

代碼

#include<iostream>
#include<cstdio>
using namespace std;
const int N=+;
int a[N],mp[N];
int n,nowwz,now,ans;
int main(){
    int t;
    scanf("%d",&t);
    while(scanf("%d",&n)!=EOF){
        for(int i=;i<=n;i++){
            scanf("%d",&a[i]);
            mp[a[i]]=i;
        }
        ans=n-;
        int now=n,nowwz=mp[now];
        for(;;){
            if(now==) break;
            now--;
            if(nowwz>mp[now]){
                ans--;
                nowwz=mp[now];
            }else break;
        }
        printf("%d\n",ans);
    }
}