当前位置:编程学习 > C/C++ >>

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; 

作者:cgl1079743846
补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,