【题解】POJ 3253 Fence Repair(贪心) 挑战程序设计日常

POJ 3253 Fence Repair 原题

【【题解】POJ 3253 Fence Repair(贪心)】https://vjudge.net/problem/POJ-3253

农场主约翰想修理牧场周围一小段篱笆。他测量了栅栏，发现他需要N(1≤N≤20,000)块木板，每块都有整数Li(1≤Li≤50,000)个单位。然后他买了一块长木板，刚好能锯进N块厚木板(也就是木板，其长度为长度Li的和)。FJ忽略了“切缝”，即锯切时锯屑失去的额外长度; 你也应该忽略它。
FJ悲伤地意识到他没有锯子来锯木头，所以他就用这块长木板来到农民Don的农场，礼貌地问他是否可以借一把锯子。
农场主唐是一个隐蔽的资本家，他没有借给FJ一把锯子，而是提出要向农场主约翰索要木板上N-1个切口的费用。切一块木头的费用正好等于它的长度。切一块21的木板要花21美分。
农夫唐然后让农夫约翰决定切割木板的顺序和位置。帮助农民约翰确定他可以用来制作N个木板的最低金额。FJ知道他可以将木板切割成不同的顺序，这将导致不同的收费，因为中间木板的长度是不同的。
输入行1:一个整数N，木板的数量行2…N+1:每一行包含一个整数，描述所需板材的长度
输出行1:一个整数:进行N-1切割必须花费的最小金额
Sample Input

3 8 5 8

Sample Output

34

提示
他想把一块长21的木板切成8、5和8的小块。
原来的棋盘是8+5+8=21。第一次切割的成本是21美元，应该用来把木板切割成13和8的大小。第二次削减将花费13，并应用于削减13成8和5。这将花费21+13=34。如果将21削减为16，将5削减为5，那么第二次削减将花费16，总共37(比34多)。
题解题意：一块整的木板，每次切都会花费当前整木板长度的费用，求最少的花费。
思路：用哈夫曼树或者是优先队列。我用的优先队列，每次都把最小的两个相加再入队，最后队列里只剩一个数时就是所要求的答案。

#include #include #define ll long long using namespace std; int main() { int n, t; cin >> n; priority_queue ,greater > que; //设一个小顶堆 for(int i = 0; i < n; i++) { cin >> t; que.push(t); //入队 } if(que.size() == 1) {//n为1时直接输出 cout << que.top(); return 0; } ll sum = 0; while(que.size() > 1) { ll minf, mins; //第一小和第二小 minf = que.top(); que.pop(); mins = que.top(); que.pop(); sum += minf + mins; //记录花费 que.push(minf + mins); //再入队 } cout << sum << endl; return 0; }