农夫约翰想修理牧场周围的一小段围栏。他测量了围栏,发现他需要N(1≤N≤20000)块木板,每块木板都有一定的整数长度Li(1≤Li≤50000)单位。然后,他购买了一块长度刚好足以锯入N块木板的长木板(即,其长度为Li长度的总和)。FJ忽略了“切口”,即锯切时锯屑损失的额外长度;你也应该忽略它。 FJ伤心地意识到他没有锯木头的锯子,于是他拿着这块长木板来到农夫唐的农场,礼貌地问他是否可以借一把锯子。 农夫唐是一位秘密资本家,他不借给FJ一把锯子,而是提议向农夫约翰收取N-1块木板的每一块费用。切割一块木头的费用正好等于它的长度。切割长度为21的木板需要21美分。 农夫唐然后让农夫约翰决定切割木板的顺序和位置。帮助农夫约翰确定他可以花多少钱来制作N块木板。FJ知道,他可以按照不同的顺序切割木板,这将导致不同的费用,因为产生的中间木板长度不同。
输入 第1行:一个整数N,木板的数量 第2..N+1行:每行包含一个整数,描述所需木板的长度 输出 第1行:一个整数:他必须花费N-1次削减的最低金额
Sample Input 3 8 5 8 Output 34
暗示 他想把一块长度为21的木板切成长度为8、5和8的几块。 原始板的尺寸为8+5+8=21。第一次切割将花费21美元,应用于将板材切割成尺寸为13和8的块。第二次切割将花费13,并且应该用于将13切割成8和5。这将花费21+13=34。如果将21号切割成16号和5号,第二次切割将花费16号,总共37号(超过34号)。
思路
将所需木板长度放入最小值优先的优先队列。如果优先队列只有一个元素,则队头为总费用。如果优先队列的元素个数大于1,则让优先队列的两个元素出队,求和后加到总费用中,再将和入队,重复直到优先队列只剩下一个元素,输出总费用。
AC代码
#include <iostream>
#include <queue>
#define AUTHOR "HEX9CF"
using namespace std;
int n;
long long cost = 0;
priority_queue<int, vector<int>, greater<int>> pq;
int main()
{
cin >> n;
while (n--)
{
int in;
cin >> in;
pq.push(in);
}
if(1 == pq.size()){
cost += pq.top();
}
while (pq.size() > 1)
{
int a, b;
a = pq.top();
pq.pop();
b = pq.top();
pq.pop();
cost += (a + b);
pq.push(a + b);
}
// cout << pq.top() << endl;
cout << cost << endl;
return 0;
}