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;
}
补充:软件开发 , C++ ,