首页 > 代码库 > poj3253 Fence Repair【优先队列】

poj3253 Fence Repair【优先队列】

2024-07-24 00:59:22   221人阅读

大意：

需要把一根长木棍锯成一些短木棍

短木棍的长度是告诉你的

每一次锯的花费为要锯的改段的长度

问最小花费

比如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 }
View Code

 

poj3253 Fence Repair【优先队列】


联系
我们