本文共 1386 字,大约阅读时间需要 4 分钟。
18905 | 34.82% | 2697 | 81.79% |
题目链接:
题目类型: 数据结构, 链表
样例输入:
23YertleDuke of EarlSir LancelotDuke of EarlYertleSir Lancelot9YertleDuke of EarlSir LancelotElizabeth WindsorMichael EisnerRichard M. NixonMr. RogersFord PerfectMackYertleRichard M. NixonSir LancelotDuke of EarlElizabeth WindsorMichael EisnerMr. RogersFord PerfectMack
样例输出:
Duke of EarlSir LancelotRichard M. NixonYertle
题目大意: 题目时希尔排序,但是和希尔排序无关。 有一堆乌龟, 从上到下叠好,各自有自己的名字。 然后题目给出两个序列, 第一个是初始序列,第二个是目标序列, 题目要求是以最少的步骤把初始序列转换成目标序列,转换的操作为:每次只能选中一只乌龟,把这个乌龟抽出来放到最顶端,其它的乌龟则全部降落一格。
解题思路: 要使步骤最少,那么要保证相对顺序是符合目标序列的不要进行移动(即最大公共子序列不要进行移动)。 可以设置两个坐标指向两个数组的最后一个,然后往前枚举,碰到相同的,则两个坐标都减1, 如果不相同的,则初始数组的坐标减一。最后指向初始数组的坐标移动到了尽头,会发现目标数组的坐标还没到尽头,那么在这个坐标之前的都是不符合顺序的,就要移动这些乌龟。 然后剩下的这些乌龟, 按目标数组的逆序输出即可。
#include#include #include #include using namespace std;char origin[250][85], result[250][85];int main(){ freopen("input.txt", "r", stdin); int T, n,i,j; scanf("%d", &T); getchar(); while(T--){ scanf("%d", &n); getchar(); for(i=0; i =0 && right>=0){ if(strcmp(origin[left], result[right])) { --left; } else --right, --left; } while(right>=0) puts(result[right--]); if(T) printf("\n"); } return 0;}
转载地址:http://tuzni.baihongyu.com/