Posted on 2013-06-12 21:37
happyac 阅读(1313)
评论(0) 编辑 收藏 引用 所属分类:
uva
总结
只利用给定的方法，$flip$，对数组排序。
分析
排序方式有很多。因为原题并没有要求最优解，所以有一个简单的思路：假设有一个长度为 $n$ 的栈：
- 找到栈中最大元素的位置，$k$
- $flip(k)$，这样最大的元素就在栈顶了
- $flip(1)$，这样最大的元素就在栈底了
- 对长度为 $n-1$ 的栈重复上面的步骤
基本的想法就是每次都把当前最大的元素放到栈底，循环 $n-1$ 次之后就排序完成了。
陷阱
$flip(k)$ 中 $k$ 是从栈底算的，栈底元素位置为 $1$，栈顶的位置为 $n$。