首页 > 其他 > 详细

[BZOJ1724][Usaco2006 Nov]Fence Repair 切割木板

时间:2019-01-02 23:14:32      阅读:31      评论:0      收藏:0      [点我收藏+]

标签:n)   rep   pop   ++   queue   reat   .com   php   algo   

题目链接:

BZOJ1724.

思维神题。

直接按照题目去解很难想出思路(贪心?\(DP\)?)

其实,把整个切割过程倒过来,你就会发现,这不就是合并果子吗。。

用小根堆维护所有木板,每次贪心取最小两个木板合并。

时间复杂度 \(O(nlog_2n)\)

#include <queue>
#include <cstdio>
#include <vector>
#include <algorithm>

int n;
std::priority_queue<int,std::vector<int>,std::greater<int> > q;

int main()
{
    scanf("%d",&n);
    for(int i=1,l;i<=n;++i)
        scanf("%d",&l),q.push(l);
    long long Ans=0;
    for(int x,y;(int)q.size()>1;)
    {
        x=q.top(),q.pop();
        y=q.top(),q.pop();
        Ans+=x+y,q.push(x+y);
    }
    printf("%lld\n",Ans);
    return 0;
}

[BZOJ1724][Usaco2006 Nov]Fence Repair 切割木板

标签:n)   rep   pop   ++   queue   reat   .com   php   algo   

原文:https://www.cnblogs.com/LanrTabe/p/10211550.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 designnerd.net 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号