首页技术正文

Boxes And Balls(三叉哈夫曼编码)

程序员建伟技术 2022年11月23日

0 收藏 920 点赞 4,099 浏览 723 个字

题目

原题链接：http://codeforces.com/problemset/problem/884/D

现有一堆小石子，要求按要求的数目分成N堆，分别为a₁、a₂、…a_n。具体的，每次选一个堆(其重量为代价)，分成2或3堆。求最小的可能代价。

思路

我们反向考虑，就是一个不断合并的过程。当n为奇数，我们总能找到三个最小的合并，直到只剩一堆；当n为偶数，先选择最小的两个合并，再按奇数一样处理。(为了统一起来，添加一个辅助堆，石子个数为0)

代码实现

 #include<stdio.h>
 #include<iostream>
 #include<queue>
 using namespace std; typedef long long ll;
 int n; int main()
 {
     while (scanf("%d",&n) == )
     {
         priority_queue<ll,vector<ll>,greater<ll> >q;
         ll ans = ;
         for (int i = ; i < n; i++)
         {
             int tmp;
             scanf("%d", &tmp);
             q.push(tmp);
         }
         if ((n & ) == )  q.push();  //n为偶数，补充一个0
         while (q.size() > )
         {
             ll a = q.top(); q.pop();
             ll b = q.top(); q.pop();
             ll c = q.top(); q.pop();
             ans += (a + b + c);
             q.push(a + b + c);
         }
         q.pop();
         printf("%I64d\n", ans);
     }
 }