首页 > 代码库 > UVa 10152 龟壳排序

UVa 10152 龟壳排序

思路:先读入的一列是原始串,后读入的一列是目标串。最少操作次数的方式是,从下到上,只对原始串进行删除而不放到最上面能得到的目标串的以最下元素开头的最长子串,然后将目标串剩余的那些按序放在最上方,即按由下到上的顺序输出即可。

Code:

//#define LOCAL
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

char name[210][90];
char target[210][90];
//char stack[210][90];

int main()
{
 #ifdef LOCAL
  freopen("10152.in","r",stdin);
  freopen("10152.out","w",stdout);
 #endif
 int k;
 scanf("%d",&k);
 while(k-->0)
 {
  memset(name,0,sizeof(name));
  memset(target,0,sizeof(target));
  int n;
  scanf("%d",&n);
  getchar();
  for(int i=0;i<n;++i)
   fgets(name[i],85,stdin);
  for(int i=0;i<n;++i)
   fgets(target[i],85,stdin);
  
  int a=n-1,b=n-1;
  //int top=-1;
  while(a>=0)
  {
   if(strcmp(target[b],name[a])==0) { a--; b--; }
   else  //{ strcpy(stack[++top],name[a--]); }      
    a--;
  }//
  for(int i=b;i>=0;--i)
   fputs(target[i],stdout);  
  fputs("\n",stdout);        
 }   
 return 0;
}