题目链接:
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1093
题目意思:
有n只乌龟,一只排在另一只的上面,告诉初始排列的乌龟的情况,而且每次只能将某一只乌龟移到最上面,告诉最终的乌龟的排列情况,问应该怎样移动乌龟使移动的乌龟的个数最少。
解题思路:
将初始次序的乌龟编号1-n,然后将最后次序的乌龟按照该编号排列。
定义两个指针,分别指向两排列的最后一个,分别为a,b,如果a,b所指向的内容相同,则将两指针都上移,否则将a指针向前移一位,知道a指不能移动为止。
此时b指针及以上内容都要移动,且移动的顺序为b指针移动的顺序。
代码:
#include<iostream> #include<cmath> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> #include<algorithm> #include<vector> #include<map> #define eps 1e-6 #define INF (1<<20) #define PI acos(-1.0) using namespace std; char begin[230][90],end[230][90]; int n; int find(int j) { for(int i=1;i<=n;i++) if(strcmp(begin[i],end[j])==0) return i; } int main() { int ca,last,flag; scanf("%d",&ca); while(ca--) { scanf("%d",&n); //注意吃掉这个回车 getchar(); for(int i=1;i<=n;i++) gets(begin[i]); for(int i=1;i<=n;i++) gets(end[i]); last=find(n); flag=0; for(int i=n-1;i>=1;i--) { int temp=find(i); //printf("temp:%d\n",temp); if(temp>last) { flag=i; break; } last=temp; } if(flag) { puts(begin[find(flag)]); //将b指针指向的内容从下至上输出 for(int i=flag-1;i>=1;i--) { puts(begin[find(i)]); } } //if(ca) putchar('\n'); } return 0; }