Canvas Painting Gym - 101128C ，优先队列，哈夫曼树

题意：要求将n块初始颜色相同的布条染成不同颜色，染色的代价即布条的大小，求最小代价。

思路：逆向思考，即将不同的布条染成一个颜色，每次只可以选两种颜色合并。求最小代价，即构造哈夫曼树。

#include <iostream> #include <algorithm> #include <queue> using namespace std; typedef long long LL; int main() { int test ; int n ; priority_queue< LL,vector<LL>,greater<LL> > que; LL sum; cin>>test; while ( test-- ) { while ( !que.empty() ) que.pop(); int t; cin>>n; while ( n-- ) { cin>>t; que.push(t); } sum =0 ; while ( que.size()!=1 ) { LL t1 = que.top(); que.pop(); LL t2 = que.top(); que.pop(); que.push( t1+t2 ) ; sum += t1+t2; } cout<<sum<<endl; } return 0; }