【题解】LOJ 2132 「NOI2015」荷马史诗

Problem

给定 $n$ 种不同的单词以及每个单词在文章中出现的次数,要求给每个单词用 $k$ 进制数进行重编码,使得编码后的文章长度尽可能的短

同时,为了能够还原信息,需要保证两两单词编码互不为前缀

求最短文章长度,以及最长的单词编码长度最短是多少

Thought

貌似是哈夫曼编码裸题啊,构建 $k$ 叉哈夫曼树

发现有可能最上面一层有空位,并且空位的数目是一开始就能计算出来的
所以用出现次数为 $0$ 的“特殊字符”补齐即可

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll read() {
    ll ans = 0, flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}

const int N = 400010;

ll n, k;

struct Edge {
    int t, n;
}e[N];
int head[N], tot;
int cnt;

ll w[N];
ll sum;

void addedge(int u, int v) {
    e[++ tot] = {v, head[u]};
    head[u] = tot;
}

struct Node {
    ll tim; int id, len;

    bool operator < (const Node x) {
        if(tim == x.tim)
            return len < x.len;
        return tim < x.tim;
    }
    void operator += (const Node x) {
        tim += x.tim;
        len = max(len, x.len + 1);
    }
};

struct Heap {
    Node p[N]; int tot;
    void push(Node x) {
        p[++ tot] = x;
        int now = tot;
        while((now >> 1) && p[now] < p[now >> 1]) {
            swap(p[now], p[now >> 1]);
            now >>= 1;
        }
    }
    void push(ll tim, int id, int len) {
        p[++ tot] = {tim, id, len};
        int now = tot;
        while((now >> 1) && p[now] < p[now >> 1]) {
            swap(p[now], p[now >> 1]);
            now >>= 1;
        }
    }
    void pop() {
        p[1] = {0, 0, 0}; p[1] = p[tot]; p[tot --] = {0, 0, 0};
        int now = 1, son = 2;
        while(son <= tot) {
            if(son + 1 <= tot && p[son + 1] < p[son]) ++ son;
            if(p[son] < p[now]) {
                swap(p[son], p[now]);
                now = son;
                son = now << 1;
            }
            else break;
        }
    }
}h;

void dfs(int x, int len) {
    if(!head[x]) sum += w[x] * len;
    for(int i = head[x]; i; i = e[i].n) {
        dfs(e[i].t, len + 1);
    }
}

int main() {
    n = read(); k = read();
    for(int i = 1; i <= n; ++ i) {
        w[i] = read();
        h.push(w[i], ++ cnt, 0);
    }
    if(n <= k)
        for(int i = 1; i <= k - n; ++ i)
            h.push(0, ++ cnt, 0);
    else {
        int last = (n - k) % (k - 1);
        if(last)
            for(int i = 1; i <= k - 1 - last; ++ i)
                h.push(0, ++ cnt, 0);
    }
    while(h.tot > 1) {
        Node merge = {0, ++ cnt, 0};
        for(int i = 1; i <= k; ++ i) {
            merge += h.p[1];
            addedge(merge.id, h.p[1].id);
            h.pop();
        }
        h.push(merge);
    }
    dfs(cnt, 0);
    printf("%lld\n", sum);
    printf("%lld\n", h.p[1].len);
    return 0;
}
Comments

添加新评论