作者Franckie ( )
看板Prob_Solve
标题Re: [问题] 一个感觉是 dynamic programming 的题目
时间Fri Apr 23 09:36:38 2010
※ 引述《locomotion (locomotion)》之铭言：
: : 题目是这样的:
: : 给定 n 个箱子, 每个箱子有其自己的 重量 以及 载重量
: : 现在要将箱子一层一层往上叠, 顺序不拘
: : 每个箱子上方所有的重量加起来不能超过自己的载重量
: : 试问, 最高可以叠到几层?
: 换个方向思考吧，不要先放最下面的那一个
: 先放最上面的那一个呢?
: 1.先将所有箱子依载重量由小到大排 (Sorting:O(nlogn))
: 2.依载重量由小到大放进list
: a.如果累积的重量比当前箱子的载重量小，将箱子放进list
: b.如果累积的重量超过当前箱子的载重量
: 将目前list中最重的箱子拿走
请问l大 2.b 这个步骤您要怎样实做呢?
这个步骤的复杂度应该不太可能是O(1)吧?
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 61.218.212.227
1F：推 Fenikso:O(logn), 用heap 04/23 09:38
2F：→ Franckie:不需要建heap的cost? 04/23 09:44
4F：→ bleed1979:用priority_queue 速度0.020s F兄的0.096s 04/23 09:50
5F：→ bleed1979:我的还在debug, 速度超慢。 04/23 09:50
6F：推 Fenikso:to 2F: 不需要 因为一开始heap是空的 04/23 12:02
7F：→ Fenikso: 然後push pop都是O(logn) 04/23 12:03
8F：推 Fenikso: total复杂度是nlogn 04/23 12:08
9F：推 suhorng:我用 std::push_heap/std::pop_heap, 0.008 04/23 21:50