首页 > 代码库 > poj3253 Fence Repair【优先队列】
poj3253 Fence Repair【优先队列】
大意:
需要把一根长木棍锯成一些短木棍
短木棍的长度是告诉你的
每一次锯的花费为要锯的改段的长度
问最小花费
比如n个小木棍长度分别5 8 8
也就是相当于你有一根21的木棍 现在需要把它锯成 上述的三段
每次只能把一个木棍锯成两段
比如21可以锯成13 和 8 但是由于选择的是21 所以花费为21
第二次把13 锯成5和8 花费 为13
总花费为21 + 13 = 34
分析:
其实我们可以逆向思维
想在有n跟木棍现在想要把他们拼成一跟
每一次的花费就是这两段的和
那么我们根据贪心的思想肯定是每次选取的是最小的两段了
用堆或优先队列来写就可以了
代码:
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <queue> 5 using namespace std; 6 7 const int maxn = 20005; 8 9 priority_queue<int, vector<int>, greater<int> > q;10 11 int main() {12 int n;13 int num;14 while(EOF != scanf("%d",&n) ) {15 while(!q.empty() ) q.pop();16 for(int i = 1; i <= n; i++) {17 scanf("%d",&num);18 q.push(num);19 }20 long long ans = 0;21 while(q.size() >= 2) {22 int x1 = q.top(); q.pop();23 int x2 = q.top(); q.pop();24 ans += x1 + x2;25 q.push(x1 + x2);26 }27 printf("%I64d\n",ans);28 }29 return 0;30 }
poj3253 Fence Repair【优先队列】
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。