Skip to content

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

题目

题目描述

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

Description

骆源,上海交通大学计算机系教授。兼任美国数学评论评论员、第五届亚欧信息论研讨会AEW5联合主席。承担过国家自然科学基金、教育部留学回国人员基金及德国国家科学基金DFG的项目。对于我们来说,骆源的离散数学课是一朵奇葩。 这道题目是骆源的哈夫曼树,哈夫曼树大家都记得是什么吧(翁老师又讲过一次,如果不记得就翻翻书吧)。但是作为骆源的哈夫曼树,自然要有些不同。骆源的哈夫曼树可以有N个分叉(注意,有时要补零!)。哈夫曼树的要求和构造方式和二叉并没有什么不同(除了要补零之外)。

为了方便,这道题并不需要你输出具体的编码,只需要你计算出最后的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

先补1个零。
哈夫曼编码:
0:00
1:01
2:02
3:1
4:2

Output=12+22+31+41=13

Hint

有时要补零。大家还记得要补几个零吗?

另外,要ac掉100%的数据,请用堆优化吧(其实就是传说中的优先级队列)另外为了表示对骆源的尊敬,不允许使用STL哦^_^。

数据范围: 对于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;
}