本文主要是介绍hunnu 10611 聪明的木匠 (优先队列)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接:点击打开链接
| 聪明的木匠 |
| Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:32768KB |
| Total submit users: 58, Accepted users: 50 |
| Problem 10611 : No special judgement |
| Problem description |
| 最近，一位老木匠遇到了一件非常棘手的问题。他需要将一根非常长的木棒切成N段。每段的长度分别为L1,L2,…,LN（ 1≤L1,L2,…,LN≤1000，且均为整数）个长度单位。∑Li(i=1,2,…,N)恰好就是原木棒的长度。我们认为切割时仅在整数点处切且没有木材损失。 木匠发现，每一次切割花费的体力与该木棒的长度成正比，不妨设切割长度为1的木棒花费1单位体力。例如，若N=3，L1=3,L2=4,L3=5，则木棒原长为12，木匠可以有多种切法，如：先将12切成3+9.，花费12体力，再将9切成4+5，花费9体力，一共花费21体力；还可以先将12切成4+8，花费12体力，再将8切成3+5，花费8体力，一共花费20体力。显然，后者比前者更省体力。 那么，木匠至少要花费多少体力才能完成切割任务呢？ |
| Input |
| 输入数据的第一行为一个整数N(2≤N≤150,000)； 在接下来的N行中，每行为一个整数Li(1≤Li≤1000)。 |
| Output |
| 输出数据仅有一行，为一个整数，表示木匠最少要花费的体力。测试数据保证这个整数不大于231-1。 |
| Sample Input |
4 3 5 7 11 |
| Sample Output |
49 |
思路: 这道题是在 51NOD 贪心哈夫曼编码里的, Huffman编码, 这只是其中的一小部分, 利用 优先队列, 哈夫曼编码,太麻烦了,对于这题直接 优先队列 就可以, 但是, 要注意 优先队列的重载;
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stdio.h>
#include <vector>using namespace std;struct cmp{bool operator () (const int &x,const int &y){return x>y;}
};priority_queue < int ,vector<int>,cmp> Q;int main()
{int i,n,val;cin>>n;for(i=0;i<n;i++){cin>>val;Q.push(val);}int sum=0;while(n>=2){int x=Q.top();Q.pop();int y=Q.top();Q.pop();sum+=x+y;Q.push(x+y);n--;}cout<<sum<<endl;return 0;
}
123
这篇关于hunnu 10611 聪明的木匠 (优先队列)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
