• 如果您想对本站表示支持,请随手点击一下广告即可~
  • 本站致力于提供原创、优秀的技术文章~
  • 有任何疑问或建议 均可以在站点右侧栏处 通过各种方式联系站长哦~
  • POJ3253 – Fence Repair

    ACM-POJ EXP 272阅读 0评论

    全解题报告索引目录 -> 【北大ACM – POJ试题分类


    大致题意

    有一个农夫要把一个木板钜成几块给定长度的小木板,每次锯都要收取一定费用,这个费用就是当前锯的这个木版的长度

    给定各个要求的小木板的长度,及小木板的个数n,求最小费用

    提示

    3

    8 8 5为例:

    先从无限长的木板上锯下长度为 21 的木板,花费 21

    再从长度为21的木板上锯下长度为5的木板,花费5

    再从长度为16的木板上锯下长度为8的木板,花费8

    总花费 = 21+5+8 =34

    解题思路

    利用Huffman思想,要使总费用最小,那么每次只选取最小长度的两块木板相加,再把这些“和”累加到总费用中即可

    本题虽然利用了Huffman思想,但是直接用HuffmanTree做会超时,可以用优先队列

    因为朴素的HuffmanTree思想是

    (1)先把输入的所有元素升序排序,再选取最小的两个元素,把他们的和值累加到总费用

    (2)把这两个最小元素出队,他们的和值入队,重新排列所有元素,重复(1),直至队列中元素个数<=1,则累计的费用就是最小费用

    HuffmanTree超时的原因是每次都要重新排序,极度浪费时间,即使是用快排。

    一个优化的处理是:

    (1)只在输入全部数据后,进行一次升序排序 (以后不再排序)

    (2)队列指针p指向队列第1个元素,然后取出队首的前2个元素,把他们的和值累计到总费用,再把和值sum作为一个新元素插入到队列适当的位置

    由于原队首的前2个元素已被取出,因此这两个位置被废弃,我们可以在插入操作时,利用后一个元素位置,先把队列指针p+1,使他指向第2个废弃元素的位置,然后把sum从第3个位置开始向后逐一与各个元素比较,若大于该元素,则该元素前移一位,否则sum插入当前正在比较元素(队列中大于等于sum的第一个元素)的前一个位置

    (3)以当前p的位置作为新队列的队首,重复上述操作

    另一种处理方法是利用STL的优先队列,priority_queue,非常方便简单高效,虽然priority_queue的基本理论思想还是上述的优化思想,但是STL可以直接用相关的功能函数实现这些操作,相对简单,详细参见我的程序。

    注意priority_queue与qsort的比较规则的返回值的意义刚好相反

    Source修正

    USACO 2006 November Gold(已失效)

    从测试数据看得到是存在大数的情况的,要使用 __int64


    方法一: 优先队列

    转载请注明:EXP 技术分享博客 » POJ3253 – Fence Repair

    喜欢 (0) 分享 (0)
    发表我的评论
    取消评论

    表情

    Hi,您需要填写昵称和邮箱!

    • 昵称 (必填)
    • 邮箱 (必填)
    • 网址