Uva 10152 ShellSort

点击打开链接

题目意思：有一堆的乌龟，输出一堆乱序的乌龟，然后输入一个正确的顺序，要求找到一种最小步骤的方法使得第一堆变成第二堆，每一次可以把乌龟移到第一个位置，输出该方法步骤.

解题思路：我们可以用两个char 数组来存储第一和第二堆的乌龟顺序，然后用两个int 数组num和tem来存储乌龟的顺序编号.我们知道只要从后面往前遍历tem数组就可以找到最小的步骤，然后利用栈的先进后出的性质(由上面可知，乌龟最后一个肯定是最先移动的）

代码：

//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;
}