2022-03-02

对于哈夫曼树和哈夫曼编码已经有所认识，此题相当于使用多叉树的哈夫曼编码方式。对于k叉树，我们可以不用树形结构而用队列来做，会更方便，哈夫曼编码又需要选择最小的k个值来结合，故我们使用优先队列，在头文件queue中，名为

priority_queue

这个STL的使用方法：

默认从大到小：priority_queue<int> a;

从小到大：priority_queue< int,vector<int>,greater<int> > b;

如果是自定义的数据结构：

struct tmp1
{
    int x;
    tmp1(int a)
         {x = a;}
    bool operator<(const tmp1& a) const
    {
        return x < a.x; 
    }
};   

注意operator要 < ，优先队列规定的

push()：插入至首位

top():首位元素

pop:删除

 

利用优先队列进行哈夫曼编码如下：

 1 #include<iostream>
 2 #include<queue>
 3 #define ll long long
 4 using namespace std;
 5 int n, k;
 6 ll sum;
 7 typedef struct Treecode {
 8     int len;
 9     ll val;
10     Treecode(int _len, ll _val)
11     {
12         len = _len;
13         val = _val;
14     }
15     inline bool operator <(const Treecode &a)const
16     {
17         if (val == a.val)
18             return a.len < len;
19         return a.val < val;
20     }
21 }htree;
22 priority_queue<htree>forest;
23 inline ll read()
24 {
25     ll x = 0;char c = getchar();
26     while (c < '0' || c>'9') c = getchar();
27     while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
28     return x;
29 }
30 int main(void)
31 {
32     int cnt;
33     cin >> n >> k;
34     if ((n - 1) % (k - 1))
35     {
36         cnt = (n - 1) % (k - 1);
37         for (int i = n + 1;i < n + 1 + cnt;i++)
38             forest.push(htree(1, 0));
39     }
40     for (int i = 1;i <= n;i++)
41     {
42         ll a = read();
43         forest.push(htree(1, a));
44     }
45     n += cnt;
46     while (n > 1)
47     {
48         ll ans = 0;
49         int maxlen = 0;
50         for (int i = 0;i < k;i++)
51         {
52             ans += forest.top().val;
53             maxlen = max(maxlen, forest.top().len);
54             forest.pop();
55         }
56         sum += ans;
57         forest.push(htree(maxlen + 1, ans));
58         n = n - k + 1;
59     }
60     cout << sum << endl;
61     cout << forest.top().len - 1;
62     return 0;
63 }