Uva 10152 ShellSort

題目意思：有一堆的烏龜，輸出一堆亂序的烏龜，然後輸入一個正確的順序，要求找到一種最小步驟的方法使得第一堆變成第二堆，每一次可以把烏龜移到第一個位置，輸出該方法步驟.

解題思路：我們可以用兩個char 數組來存儲第一和第二堆的烏龜順序，然後用兩個int 數組num和tem來存儲烏龜的順序編號.我們知道只要從後面往前遍歷tem數組就可以找到最小的步驟，然後利用棧的先進後出的性質(由上面可知，烏龜最後一個肯定是最先移動的）

代碼：
[cpp] 
//UVA10152 
#include <cstdio> 
#include <cstring> 
#include <iostream> 
#include <stack> 
#include <map> 
#include <algorithm> 
using namespace std; 
 
char ch[210][100] , temp[210][100]; 
int  num[210] , tem[210]; 
 
void output(int n){ 
    int i , j; 
    memset(tem , 0 ,sizeof(tem)); 
    for(i = 0 ; i < n ;i++){ 
        for(j = 0 ; j < n ; j++){ 
            if(strcmp(temp[i] , ch[j]) == 0) 
                tem[i] = num[j]; 
        } 
    } 
    for(i = n-2 ;i >= 0 ; i--){ 
        if(tem[i] > tem[i+1]) 
            break; 
    } 
    stack<char*>s; 
    for(j = 0 ;j <= i ;j++) 
        s.push(temp[j]); 
    while(!s.empty()){ 
        cout<<s.top()<<endl; 
        s.pop(); 
    } 
    cout<<endl; 
} 
int main(){ 
    int t , n , i , j; 
    cin>>t; 
    while(t--){ 
        int n; 
        cin>>n; 
        getchar(); 
        memset(num , 0 , sizeof(num)); 
        for(i = 0 ;i < n ; i++){ 
            gets(ch[i]); 
            num[i] = i; 
        } 
        for(i = 0 ; i < n ; i++){ 
            gets(temp[i]); 
        } 
        output(n); 
    } 
    return 0; 
}