首页 > 代码库 > sgu-203 Hyperhuffman

sgu-203 Hyperhuffman

2024-08-09 16:42:31   214人阅读

题目大意：
给出一个n，表示一篇文章中的不同单词的个数为n，然后接下来给出n个整数，表示各个单词出现的频率，要你求对这篇文章的所有单词huffman转码后的文章的长度。


解题思路：
首先看到这道题目准备直接去构造huffman tree，但是后来懒得写（其实是我太渣），然后脑补了一下发现了什么：
这道题目实际上不需要建树，因为只要求huffman tree 的权值（就是每个叶子节点的权值乘以对应深度）。所以我们想到了用另一个好东西——小根堆！！！！！

但是如何用小根堆做呢？我们观察一下huffman tree 的权值，会发现也等于每个节点的权值和，根据这个道理，我们可以当小根堆中的元素个数大于1时，将最小的两个合并成一个，权值相加，然后将这个点重新插入堆中，ans+=v[i]+v[j]（两个合并的权值），然后当只剩下一个元素的时候就跳出循环输出ans就行了


AC代码：

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>

using namespace std;
long long a[500010]={0};
long long ans=0;
int n;

void tz(int k)
{
	long long p=(long long)2e19,q=(long long)2e19;
	if(k*2<=n) p=a[k*2];
	if(k*2+1<=n) q=a[k*2+1];
	if(p<=q && p<=a[k])
	{
		swap(a[k],a[k*2]);
		tz(k*2);
	}
	else if(q<=p && q<=a[k])
	{
		swap(a[k*2+1],a[k]);
		tz(k*2+1);
	}
	return;
}

int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		scanf("%I64d",&a[i]);
	sort(a+1,a+n+1);
	for(;n>1;)
	{
		long long x1=a[1];
		swap(a[1],a[n]);
		n--;
		tz(1);
		long long x2=a[1];
		ans+=x1+x2;
		a[1]=x1+x2;
		tz(1);
	}
	printf("%I64d\n",ans);
	return 0;
}


sgu-203 Hyperhuffman


联系
我们