# 13020: 【原3020】骆源的哈夫曼树

### 题目描述

author: gaoji 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/3020

4 3
1
2
3
4

13

## Sample Explanation

０：００
１：０１
２：０２
３：１
４：２

Output=12+22+31+41=13

## 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();
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>
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++) {
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);
}

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;

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];