uva 10152 ShellSort 龜殼排序（希爾排序？）

今天狀態總是很糟，這種題目卡了一天。。。

是不是休息時間太少了，頭腦遲鈍了。。。

名字叫希爾排序，我還以為跟它有關，還搜索了下資料。

只要找到trick就會發現是很水的題目。只要對比下就能找到哪些是移動過的龜殼，然後輸出就行了。

代碼：

#include <cstdio>  
#include <cstring>  
const int maxn = 1000; 
char pre[maxn][100], tar[maxn][100]; 
 
int main() { 
    int n; 
//  freopen("in", "r", stdin);  
    scanf("%d", &n); 
    while (n--) { 
        int m; 
        scanf("%d", &m); 
        gets(pre[0]); 
        for (int i = m - 1; i >= 0; i--) 
            gets(pre[i]); 
        for (int i = m - 1; i >= 0; i--) 
            gets(tar[i]); 
        int cnt = 0; 
        for (int i = 0, j = 0; i < m;) { 
            if (!strcmp(pre[i], tar[j])) 
                i++, j++; 
            else 
                i++, cnt++; 
        }//for  
        for (int i = m - cnt; i < m; i++) 
            printf("%s\n", tar[i]); 
        printf("\n"); 
    }//while  
    return 0; 
} 

#include <cstdio>
#include <cstring>
const int maxn = 1000;
char pre[maxn][100], tar[maxn][100];

int main() {
 int n;
// freopen("in", "r", stdin);
 scanf("%d", &n);
 while (n--) {
  int m;
  scanf("%d", &m);
  gets(pre[0]);
  for (int i = m - 1; i >= 0; i--)
   gets(pre[i]);
  for (int i = m - 1; i >= 0; i--)
   gets(tar[i]);
  int cnt = 0;
  for (int i = 0, j = 0; i < m;) {
   if (!strcmp(pre[i], tar[j]))
    i++, j++;
   else
    i++, cnt++;
  }//for
  for (int i = m - cnt; i < m; i++)
   printf("%s\n", tar[i]);
  printf("\n");
 }//while
 return 0;
}