聚合国内IT技术精华文章,分享IT技术精华,帮助IT从业人士成长

UVa 120 Stacks of Flapjacks

2013-06-14 01:20 浏览: 1267744 次 我要评论(0 条) 字号:

总结

只利用给定的方法,$flip$,对数组排序。

分析

排序方式有很多。因为原题并没有要求最优解,所以有一个简单的思路:假设有一个长度为 $n$ 的栈:
  1. 找到栈中最大元素的位置,$k$
  2. $flip(k)$,这样最大的元素就在栈顶了
  3. $flip(1)$,这样最大的元素就在栈底了
  4. 对长度为 $n-1$ 的栈重复上面的步骤
基本的想法就是每次都把当前最大的元素放到栈底,循环 $n-1$ 次之后就排序完成了。

陷阱

$flip(k)$ 中 $k$ 是从栈底算的,栈底元素位置为 $1$,栈顶的位置为 $n$。

happyac 2013-06-13 11:37 发表评论


网友评论已有0条评论, 我也要评论

发表评论

*

* (保密)

Ctrl+Enter 快捷回复