UVa 10152 ShellSort

  题目大意:给一个栈,从上到下可以表示成一个序列,可以对其进行如下操作:将其中一个元素移到顶部。给你一个初始序列和目的序列,求让初始序列变为目的序列的最小操作次数,给出一个可能的操作步骤。

  将目的序列从0到n-1进行编号,然后按这个<字符串,号码>元组对初始序列编号,得到一个序列s,对序列s从右向左扫描,找出从n-1开始的递减序列(递减值为1),将不在这个递减序列里的数剔除出来并排序,从大到小输出编号对应的字符串就行。代码如下:

View Code
 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 const int maxn = 200+10;
 7 char name[maxn][90];
 8 
 9 int main()
10 {
11 #ifdef LOCAL
12     freopen("in", "r", stdin);
13 #endif
14     int K, n;
15     scanf("%d", &K);
16     while (K--)
17     {
18         scanf("%d", &n);
19         getchar();
20         for(int i = 0; i < n; i++)
21             gets(name[i]);
22         int order[maxn], index[maxn];
23         char s[90];
24         for(int i = 0; i < n; i++)
25         {
26             gets(s);
27             for(int j = 0; j < n; j++)
28                 if(strcmp(s, name[j]) == 0)
29                 {
30                     order[j] = i;
31                     index[i] = j;
32                     break;
33                 }
34         }
35         int p = n-1;
36         int len = 0;
37         int drop[maxn];
38         for(int i = n-1; i >= 0; i--)
39         {
40             if(order[i] == p)   p--;
41             else   drop[len++] = order[i];
42         }
43         sort(drop, drop+len);
44         for(int i = len-1; i >= 0; i--)
45         {
46             printf("%s\n", name[index[drop[i]]]);
47         }
48         printf("\n");
49     }
50     return 0;
51 }
原文地址:https://www.cnblogs.com/xiaobaibuhei/p/3065968.html