12100: 【原2100】哈夫曼树
题目
题目描述
author: tomtao 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/2100
Description
饼意最近被选做助教，他有天晚上没有事情干，就无聊，顺手翻了翻数据结构书，看到了一个叫做哈夫曼树的东西。看了一会儿，饼意突然想到最近正好可以用这个去和妹子发短信，但是由于饼意的妹子不了解哈夫曼树，所以饼意要写一份清单给妹子，但是饼意不知道要准备多少大的纸，所以他拜托你来写一个程序，帮他计算所有可能用到的词的哈夫曼编码的总长度，以方便他准备纸的大小。当然由于饼意的短信太过于肉麻，所以他不会告诉你他的词是什么，他只能告诉你他有几个词（N），频率分别是多少（F[i]）。 哈夫曼编码：对于每一个词，给于一个由0、1组成的有限字符串。并且对于任意两个词，它们所对应的有限字符串s[i]、s[j]，我们有s[i]不是s[j]的前缀，s[j]也不是s[i]的前缀。我们的目标，是使得对于每一个词它的对应字符串长度乘以它出现的概率的总合最小。即 \( \min{\sum_{ 1 }^{ N }{ F[i] \times len[i] }} \) 。其中F[i]表示出现的概率，len[i]表示词对应字符串的长度，N为可能出现词的数目。
Input Format
第一行为一个数，\( N \leq 50000 \)。表示他的短信中涉及词的个数。 接下来N行，每行1个数，\( F[i] \leq 10000 \)，表示他用这个词的概率是多少。为方便起见，概率用一个非负整数表示。当然他用这个词的概率为\( \frac { F[i] }{ \sum_{ 1 }^{ N }{ F[i] } } \)。当然有些词i的概率有可能为0，但是概率为0并不代表不可能出现。
Output Format
为一个数，表示饼意所用到的所有词汇的平均长度在 \( {\sum_{ 1 }^{ N }{ F[i] \times len[i] }} \)。
为方便起见，不除以\( \sum_{1}^{N}{F[i]} \)。
Sample Input
3
1
2
3
Sample Output
9
Sample Explanation
哈夫曼编码：
1：00 len[1] = 2
2：01 len[2] = 2
3：1 len[3] = 1
Output = len[1] * F[1]+len[2]*F[2] + len[3]*F[3] = 2 * 1 + 2 * 2 + 1 * 3）
Limits
Time limit: 1000ms, memory limit: 50000kb.
q4x3's solution
/**
* 最小堆 + 哈夫曼
* 每次把最小的两个取出来加到一起
* 加入ans
* 并放回堆中
**/
#include <iostream>
#include <stdio.h>
using namespace std;
long long int N, F[50233], ans;
void down(long long int rt, long long int size) {
long long int tmp = F[rt];
if((rt << 1) > size) return;
else if((rt << 1 | 1) > size) {
if(tmp > F[rt << 1]) {
F[rt] = F[rt << 1];
F[rt << 1] = tmp;
}
return;
} else {
long long int chi1 = F[rt << 1], chi2 = F[rt << 1 | 1];
if(chi1 < tmp && chi1 <= chi2) {
F[rt] = chi1;
F[rt << 1] = tmp;
down(rt << 1, size);
} else if(chi2 < tmp && chi2 <= chi1) {
F[rt] = chi2;
F[rt << 1 | 1] = tmp;
down(rt << 1 | 1, size);
}
}
}
void build() {
for(long long int i = N / 2;i > 0;-- i) {
down(i, N);
}
}
void op(long long int size) {
long long int head = F[1];
F[1] = F[size];
down(1, size - 1);
F[1] += head; ans += F[1];
down(1, size - 1);
}
int main() {
scanf("%lld", &N);
for(long long int i = 1;i <= N;++ i)
scanf("%lld", &F[i]);
build();
for(long long int i = 0;i < N - 1;++ i) {
op(N - i);
}
cout << ans << endl;
return 0;
}
victrid's solution
#include <cstdio>
#include <iostream>
using namespace std;
int N;
struct node {
int value;
int index;
bool isleaf;
node* left;
node* right;
node& operator=(const node& rhs) {
if (this == &rhs)
return *this;
value = rhs.value;
index = rhs.index;
left = rhs.left;
right = rhs.right;
return *this;
}
};
void swap(node& n1, node& n2) {
node tmp = n1;
n1 = n2;
n2 = tmp;
return;
}
node* strage[200000];
void siftup(int nodec) {
if (nodec == 1 || nodec == 0)
return;
if (strage[nodec]->value < strage[nodec >> 1]->value) {
swap(strage[nodec], strage[nodec >> 1]);
siftup(nodec >> 1);
}
return;
}
void heapify(int nodec, int treesize) {
if (nodec >= treesize)
return;
if (nodec << 1 <= treesize && strage[nodec]->value > strage[nodec << 1]->value) {
swap(strage[nodec], strage[nodec << 1]);
heapify(nodec << 1, treesize);
}
if ((nodec << 1 | 1) <= treesize && strage[nodec]->value > strage[nodec << 1 | 1]->value) {
swap(strage[nodec], strage[nodec << 1 | 1]);
heapify(nodec << 1 | 1, treesize);
}
return;
}
node* construct() {
scanf("%d", &N);
if (N == 0)
return nullptr;
for (int i = 1; i <= N; i++) {
strage[i] = new node;
scanf("%d", &(strage[i]->value));
strage[i]->index = i;
strage[i]->left = nullptr;
strage[i]->right = nullptr;
strage[i]->isleaf = true;
}
for (int i = 2; i <= N; i++) {
siftup(i);
}
int treestrt = N;
while (treestrt != 1) {
node* ptrf = strage[1];
strage[1] = strage[treestrt];
treestrt--;
heapify(1, treestrt);
node* vs = new node;
vs->value = ptrf->value + strage[1]->value;
vs->left = ptrf;
vs->right = strage[1];
vs->isleaf = false;
strage[1] = vs;
heapify(1, treestrt);
}
return strage[1];
}
long long answ = 0;
void traverse(node* root, int level) {
if (root->isleaf) {
answ += level * root->value;
return;
}
if (root->left != nullptr)
traverse(root->left, level + 1);
if (root->right != nullptr)
traverse(root->right, level + 1);
}
int main() {
node* ans = construct();
if (ans != nullptr)
traverse(ans, 0);
printf("%lld", answ);
return 0;
}
yyong119's solution
#include <algorithm>
#include <cstdio>
const int MAXN = 50010;
int a[MAXN];
void HeapAdjust(int i , int size) {
for (;i <= (size >> 1);) {
int L = i << 1, R = i << 1 | 1, maxIndex = i;
if (a[maxIndex] > a[L] && L <= size) maxIndex = L;
if (a[maxIndex] > a[R] && R <= size) maxIndex = R;
if (maxIndex != i) std::swap(a[i], a[maxIndex]);
else break;
i = maxIndex;
}
}
int main() {
int size; scanf("%d", &size);
for (int i = 1; i <= size; ++i) scanf("%d", &a[i]);
for (int i = (size >> 1); i > 0; --i) HeapAdjust(i, size);
int tmp = size, temp = 0; long long ans = 0;
for (int i = 1; i < size; ++i) {
temp = a[1];
a[1] = a[tmp--];
HeapAdjust (1, tmp);
a[1] += temp;
ans += a[1];
HeapAdjust (1, tmp);
}
printf("%lld\n", ans);
return 0;
}