链接:
https://ac.nowcoder.com/acm/contest/924/C
题意:
农民 John 希望修复围绕农场的一小段围栏。他测量了一下,发现需要N (1 <= N <= 20,000) 根木头,每根都有某一个整数长度 Li (1 <= Li <= 50,000) 单位长度。他买了一根很长的很长的木头,正好能够锯出他所需要的N根木头。(即它的长度正好等于Li的总和) FJ 忽略锯口,锯掉的木屑产生的长度损失忽略不计,你也可以忽略它。
FJ 遗憾的发现他自己没有用于切木头的锯子,所以他就带着那根很长的木头来到了农民 Don的农场,想问他借一个锯子。
农民 Don是一个保守的资本家,他不愿意借锯子给 FJ ,但愿意自己来切这N-1刀,每一次都向FJ收取费用。每次的收费正好等于你要锯的那根木头的总长度。例如,你要锯一根长度为21的木头,就花费21分钱。
农民 Don 然后让农民 John 自己决定每次锯木头的顺序和位置。帮助农民 John 确定锯出这N根木头的最小总花费。 FJ 知道可以有很多种不同的切割方式,不同的方式可能得到不同的总花费,这是因为木头在锯的过程中的长度不一。
思路:
切成最小可以看成每次合并最小的两个木头。
代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAXN = 3e5 + 10;
const int MOD = 1e9 + 7;
int n, m, k, t;
int main()
{
// freopen("test.in", "r", stdin);
priority_queue<LL, vector<LL>, greater<LL> > que;
cin >> n;
for (int i = 1;i <= n;i++)
cin >> m, que.push(m);
LL res = 0;
while (que.size() > 1)
{
int a = que.top();
que.pop();
int b = que.top();
que.pop();
res += a+b;
que.push(a+b);
}
cout << res << endl;
return 0;
}