UVa 120

Stacks of Flapjacks

from Volume 1. Elementary Problem Solving :: Sorting/Searching

Description

对于一个栈， 有一种操作方法 Flip(x)。该方法可以将栈顶的 x 个元素反转。给出一个栈序列（从上到下）， 要求通过操作使其越接近栈顶的元素越小。输出按操作的先后顺序， 输出操作数 x 。

Solution

直接以输入序列的方式来看这题。则题目要求通过 Flip(x) 操作， 使得输入序列变为升序。因为 Flip（x） 不会影响 x 位之后的元素，所以从最后一位开始， 每次找到要调换到该位置的极大值，利用 Flip(pos) （pos为该极大值所在的位置）， 将其调到最前。然后利用 Flip(x) 将其调到对应的位置。之后再去操作前一位， 直到全部操作完为止即可。