3 条题解

  • 1
    @ 2026-10-26 9:25:45

    这里主要介绍一下哈夫曼树。

    话说为什么都复习初赛了却不知道哈夫曼树?

    本质上就是一颗 kk 叉树,每个节点连向下一层的边权从 00 到 k−1k-1,而每个叶子节点为一个词,这样就能保证不会有词是其他词的前缀(因为它的前缀不是叶子节点)。

    而一个词所对应的编码则由从根节点到这个叶子结点的路径边权拼接而成。

    --------------------------我是分隔线--------------------------

    对于最后一层可能不放满的情况,只需要加几个出现次数为 0 的点,使它最后一层能凑齐 kk 个点即可。

    而对与合并过程中出现两个相同权值的情况,只需要先合并深度小的即可。

    code:

    #include<bits/stdc++.h>
    using namespace std;
    #define int long long
    int n,k,a[100005];
    struct node{
    	int x,depth;
    };
    bool operator < (node a,node b){
    	if(a.x!=b.x) return a.x>b.x;
    	return a.depth>b.depth;
    }
    node makenode(int x,int y){
    	node aa;
    	aa.x=x; aa.depth=y;
    	return aa;
    }
    priority_queue<node> pq;
    signed main(){
    	cin>>n>>k;
    	for(int i=1;i<=n;i++){
    		cin>>a[i];
    		pq.push(makenode(a[i],0));
    	}
    	if(k!=2){
    		for(int i=n%(k-1);i!=1;i=((i+1)%(k-1))){
    			pq.push(makenode(0,0));
    		}
    	}
    	int ans=0;
    	while(pq.size()>1){
    		int max_dep=0,sum=0;
    		for(int i=1;i<=k;i++){
    			node x=pq.top();
    			pq.pop();
    			max_dep=max(max_dep,x.depth);
    			sum+=x.x;
    		}
    		pq.push(makenode(sum,max_dep+1));
    		ans+=sum;
    	}
    	cout<<ans<<'\n'<<pq.top().depth;
    	return 0;
    }
    

    信息

    ID
    939
    时间
    1000ms
    内存
    256MiB
    难度
    9
    标签
    (无)
    递交数
    123
    已通过
    11
    上传者