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$。