13020: 【原3020】骆源的哈夫曼树
题目
题目描述
author: gaoji 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/3020
Description
骆源，上海交通大学计算机系教授。兼任美国数学评论评论员、第五届亚欧信息论研讨会AEW5联合主席。承担过国家自然科学基金、教育部留学回国人员基金及德国国家科学基金DFG的项目。对于我们来说，骆源的离散数学课是一朵奇葩。 这道题目是骆源的哈夫曼树，哈夫曼树大家都记得是什么吧（翁老师又讲过一次，如果不记得就翻翻书吧）。但是作为骆源的哈夫曼树，自然要有些不同。骆源的哈夫曼树可以有Ｎ个分叉（注意，有时要补零！）。哈夫曼树的要求和构造方式和二叉并没有什么不同（除了要补零之外）。
为了方便，这道题并不需要你输出具体的编码，只需要你计算出最后的WPL＝∑F[i]×len[i] （带权路径长度，实际上就是所有编码的长度乘上权值。）即可。
Input Format
第一行为两个整数N、M，N≤100000。表示数据的数量，1<M≤1000，表示哈夫曼树的分叉数。 接下来N行，每行1个数，F[i]≤10000，表示第i个数据的权值。
Output Format
一行, 一个整数, 代表WPL的值。保证结果在long long的范围内。
Sample Input
4 3
1
2
3
4
Sample Output
13
Sample Explanation
先补１个零。
哈夫曼编码：
０：００
１：０１
２：０２
３：１
４：２
Output=12+22+31+41=13
Hint
有时要补零。大家还记得要补几个零吗？
另外，要ac掉１００％的数据，请用堆优化吧(其实就是传说中的优先级队列)另外为了表示对骆源的尊敬，不允许使用ＳＴＬ哦^_^。
数据范围: 对于30%的数据， n <= 1000。另外，对于50%的数据，m=2。
FineArtz's solution
/* 骆源的哈夫曼树 */
#include <iostream>
using namespace std;
template <class T>
class Heap{
private:
T a[200005];
int heapsize = 0;
void swap(int x, int y){
T t = a[x];
a[x] = a[y];
a[y] = t;
}
void siftup(int x){
while (x != 1){
if (a[x] < a[x >> 1]){
swap(x, x >> 1);
x >>= 1;
}
else
break;
}
}
void siftdown(){
int i = 2;
while (i <= heapsize){
if (i + 1 <= heapsize && a[i + 1] < a[i])
++i;
if (a[i] < a[i >> 1]){
swap(i, i >> 1);
i <<= 1;
}
else
break;
}
}
public:
void push(T x){
a[++heapsize] = x;
siftup(heapsize);
}
void pop(){
swap(1, heapsize);
--heapsize;
siftdown();
}
T top(){
return a[1];
}
bool empty(){
return heapsize == 0;
}
int size(){
return heapsize;
}
};
int n, m;
Heap<long long> heap;
long long ans = 0;
int main(){
cin >> n >> m;
for (int i = 1; i <= n; ++i){
long long t;
cin >> t;
heap.push(t);
}
long long t = n;
while (t > m){
t -= m;
++t;
}
if (t != 0)
for (int i = t; i < m; ++i)
heap.push(0);
while (heap.size() != 1){
long long k = 0;
for (int i = 1; i <= m; ++i){
k += heap.top();
heap.pop();
}
ans += k;
heap.push(k);
}
cout << ans << endl;
return 0;
}
Neight99's solution
#include <iostream>
using namespace std;
const int maxN = 1e6 + 100;
int N, M;
long long WPL = 0;
struct HfNode {
long long data, sum, depth;
HfNode(long long d = 0, long long s = 0, long long de = 0)
: data(d), sum(s), depth(de) {}
HfNode(const HfNode &right)
: data(right.data), sum(right.sum), depth(right.depth) {}
bool operator<(const HfNode &other) const {
if (data == other.data) {
return depth > other.depth;
}
return data < other.data;
}
HfNode &operator=(const HfNode &other) {
if (&other != this) {
data = other.data;
sum = other.sum;
depth = other.depth;
}
return *this;
}
};
template <class Type>
class priorityQueue {
private:
int currentSize;
Type *array;
int maxSize;
void doubleSpace();
void buildHeap();
void percolateDown(int);
public:
priorityQueue(int capacity = 2 * maxN);
priorityQueue(const Type *data, int size);
~priorityQueue();
bool isEmpty() const;
void enQueue(const Type &x);
Type deQueue();
Type getHead() const;
int Size() const { return currentSize; }
};
template <class Type>
priorityQueue<Type>::priorityQueue(int capacity)
: maxSize(capacity), currentSize(0) {
array = new Type[capacity];
}
template <class Type>
priorityQueue<Type>::priorityQueue(const Type *data, int size)
: maxSize(size + 10), currentSize(size) {
array = new Type[maxSize];
for (int i = 0; i < size; i++) {
array[i + 1] = data[i];
}
buildHeap();
}
template <class Type>
priorityQueue<Type>::~priorityQueue() {
delete[] array;
}
template <class Type>
bool priorityQueue<Type>::isEmpty() const {
return currentSize == 0;
}
template <class Type>
Type priorityQueue<Type>::getHead() const {
return array[1];
}
template <class Type>
void priorityQueue<Type>::enQueue(const Type &x) {
if (currentSize == maxSize - 1) {
// doubleSpace();
}
int hole = ++currentSize;
for (; hole > 1 && x < array[hole / 2]; hole /= 2) {
array[hole] = array[hole / 2];
}
array[hole] = x;
}
template <class Type>
Type priorityQueue<Type>::deQueue() {
Type minItem;
minItem = array[1];
array[1] = array[currentSize--];
percolateDown(1);
return minItem;
}
template <class Type>
void priorityQueue<Type>::percolateDown(int hole) {
int child;
Type tmp = array[hole];
for (; hole * 2 <= currentSize; hole = child) {
child = hole * 2;
if (child != currentSize && array[child + 1] < array[child]) {
child++;
}
if (array[child] < tmp) {
array[hole] = array[child];
} else {
break;
}
}
array[hole] = tmp;
}
template <class Type>
void priorityQueue<Type>::doubleSpace() {
Type *tmp = array;
maxSize *= 2;
array = new Type[maxSize];
for (int i = 0; i < currentSize; i++) {
array[i] = tmp[i];
}
delete[] tmp;
}
template <class Type>
void priorityQueue<Type>::buildHeap() {
for (int i = currentSize / 2; i > 0; i--) {
percolateDown(i);
}
}
priorityQueue<HfNode> que;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> N >> M;
for (int i = 0; i < N; i++) {
long long d;
cin >> d;
HfNode temp(d);
que.enQueue(temp);
}
if ((N - M) % (M - 1)) {
int tmp = (M - 1) - (N - M) % (M - 1);
for (int i = 0; i < tmp; i++) {
HfNode temp;
que.enQueue(temp);
}
}
while (que.Size() > 1) {
HfNode sum, temp;
for (int i = 0; i < M; i++) {
temp = que.getHead();
que.deQueue();
sum.data += temp.data;
sum.sum += temp.data + temp.sum;
if (sum.depth <= 0 || sum.depth < temp.depth + 1) {
sum.depth = temp.depth + 1;
}
}
if (sum.data == 0) {
sum.depth--;
}
que.enQueue(sum);
}
WPL = que.getHead().sum;
cout << WPL;
return 0;
}
q4x3's solution
/**
* 最小堆
* 加多少个零需要思考
**/
#include <iostream>
#define ll long long
using namespace std;
ll M, N;
ll F[101000], ans;
void down(ll rt, ll size) {
ll 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 {
ll 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(ll i = N / 2;i > 0;-- i) {
down(i, N);
}
}
void op(ll size) {
ll tmp = 0;
for(ll i = 1;i < M;++ i) {
tmp += F[1];
F[1] = F[size];
down(1, -- size);
}
tmp += F[1];
ans += tmp;
F[1] = tmp;
down(1, size);
}
int main() {
scanf("%lld%lld", &N, &M);
for(ll i = 1;i <= N;++ i) scanf("%lld", &F[i]);
ll tmp = M;
while(tmp <= N) tmp *= M;
tmp /= M;
if((N - tmp) * M % (M - 1)) tmp = (N - tmp) * M / (M - 1) + 1;
else tmp = (N - tmp) * M / (M - 1);
tmp = M - tmp % M;
if(tmp != M) N += tmp;
build();
for(ll i = 0;i < N - 1;i += (M - 1)) {
op(N - i);
}
cout << ans << endl;
}
victrid's solution
#include <cstdio>
#include <iostream>
using namespace std;
long long strage[400005];
int treesize;
void swap(long long& a1, long long& a2) {
if (a1 != a2) {
a1 ^= a2;
a2 ^= a1;
a1 ^= a2;
}
return;
};
void insert(long long i) {
strage[++treesize] = i;
int x = treesize;
while (x != 1) {
if (strage[x] < strage[x >> 1]) {
swap(strage[x], strage[x >> 1]);
x >>= 1;
} else
break;
}
return;
}
long long pop() {
swap(strage[1], strage[treesize]);
treesize--;
int i = 2;
while (i <= treesize) {
if ((i | 1) <= treesize && strage[i | 1] < strage[i])
i |= 1;
if (strage[i] < strage[i >> 1]) {
swap(strage[i], strage[i >> 1]);
i <<= 1;
} else
break;
}
return strage[treesize + 1];
}
int main() {
int n, m, a;
scanf("%d%d", &m, &n);
int p = m - (m - 2 * n) / (n - 1) * (n - 1);
while (p > n)
p -= (n - 1);
p = (n - p) % n;
treesize = 0;
while (p--) {
insert(0);
}
while (m--) {
scanf("%d", &a);
insert(a);
}
long long tot = 0, cur;
while (treesize != 1) {
cur = 0;
for (int i = 0; i < n; i++) {
cur += pop();
}
tot += cur;
insert(cur);
}
printf("%lld", tot);
return 0;
}
yyong119's solution
#include <cstdio>
#include <iostream>
#define SIZE 200000
using namespace std;
int total_node_number, branch_number, heap[SIZE], zero_number, heap_size, node_number, tmp;
long long result = 0;
void UpdateHead() {
for (int i = 1, j = 2; j < heap_size; i = j, j = i << 1) {
if (j + 1 < heap_size && heap[j + 1] < heap[j]) ++j;
if (heap[j] >= heap[i]) break;
heap[i] ^= heap[j] ^= heap[i] ^= heap[j];
}
}
void UpdateTail() {
for (int j = heap_size - 1, i = j >> 1; j > 1 && heap[i] > heap[j]; j = i, i >>= 1)
heap[i] ^= heap[j] ^= heap[i] ^= heap[j];
}
int main() {
scanf("%d%d", &total_node_number, &branch_number);
zero_number = ((branch_number - 1) - (total_node_number - 1) % (branch_number - 1)) % (branch_number - 1);
for (heap_size = 1; heap_size <= zero_number; ++heap_size)
heap[heap_size] = 0;
for (int k = 0; k < total_node_number; ++k) {
scanf("%d", &heap[heap_size++]);
UpdateTail();
}
while (heap_size > 2) {
node_number = 0;
for (int k = 0; k < branch_number; ++k) {
node_number += heap[1];
heap[1] = heap[--heap_size];
UpdateHead();
}
result += node_number;
heap[heap_size++] = node_number;
UpdateTail();
}
cout << result;
return 0;
}