http://poj.org/problem?id=3253
题意简单。
有点难想到,不过学过数据结构的都知道。
这题求的就是 huffman树合并的费用。
code:
#include <cstdio> #include <queue> #include <vector> typedef long long LL; using namespace std; int n; priority_queue<int, vector<int>, greater<int> > q; int main() { int i, t, s1, s2, x; LL ans; scanf("%d",&n); for(i=0; i<n; i++) { scanf("%d",&x); q.push(x); } ans = 0; for(i=1; i<n; i++) { s1 = q.top(); q.pop(); s2 = q.top(); q.pop(); t = s1 + s2; ans += t; q.push(t); } printf("%I64d\n",ans); return 0; }