UVa 10152

ShellSort

from Volume 2. Data Structures :: Lists

Description

• 有 n 只乌龟排成一个竖列。
• 每次只能把一只乌龟提到最上面。

输入 n 只乌龟的初始排列和目标排列，输出操作次数最少的操作。

Solution

由于越后面提出来的乌龟会放在越上面，最后一只提出来的乌龟会放在最上面。可以利用栈相似的性质——后进先出。将目标排列中的乌龟从上往下一个个放到栈里，直到剩下的乌龟刚好和目标排列一致，便不必要再操作了，并且肯定是操作次数最少的(不知道怎么表达，可以认为去操作乌龟放入栈中是必须的，而剩下不必要再动的乌龟是无须操作的，仅做了必须要做的操作，自然是最少的)。最后将乌龟一个个从栈中弹出，便是所求的操作。