题解 | #神奇编码#

根据霍夫曼树的构建方法，我们容易想到，把 $(val,dep,num)$ 看作一个三元组，分别表示当前根的值，树高，等价类个数

我们有一个贪心的做法，在val相同时，选择两个最小的dep树合并，如果 $num\ge 2$ 就是自己和自己合并，如果是奇数个则拆出来单独一个

用优先队列维护，时间复杂度: $O(n\log V\log n)$

还不能通过此题

继续观察性质，发现三元组的val递增，于是我们就可以使用同[NOIP2016 提高组] 蚯蚓同样的思路

开两个queue维护就消去了优先队列的log

时间复杂度: $O(n\log V)$

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define fr first
#define sc second
using i64 = long long;
inline int rd(void) {
    int s = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-')
            f = 0;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        s = s * 10 + c - '0';
        c = getchar();
    }
    return f ? s : -s;
}
const int N = 1e5 + 10;
struct node {
    int val, dep, num;
    inline bool operator<(const node &o) const {
        if (val != o.val)
            return val < o.val;
        return dep < o.dep;
    }
    inline node operator+(const node &o) const {
        return (node){val + o.val, max(dep, o.dep) + 1, 1};
    }
};

int n, b[N];
node ans;

bool posi;

struct Heap {
    deque<node> q[2];

    bool empty() { return q[0].empty() && q[1].empty(); }

    node top() {
        if (q[0].empty() | q[1].empty())
            return q[posi = q[0].empty()].front();
        return q[0].front() < q[1].front() ? (posi = 0, q[0].front())
                                           : (posi = 1, q[1].front());
    }
} heap;

signed main() {
    n = rd();
    for (int i = 1; i <= n; i++) {
        b[i] = rd();
        if (b[i])
            heap.q[0].push_back({i, 0, b[i]});
    }
    while (!heap.empty()) {
        node k = heap.top();
        heap.q[posi].pop_front();
        if (k.num == 1) {
            if (heap.empty()) {
                cout << k.dep << endl;
                break;
            }
            node k2 = heap.top();
            heap.q[posi].pop_front();
            k2.num--;
            if (k2.num)
                heap.q[posi].push_front(k2);
            heap.q[1].push_back(k + k2);
            continue;
        }
        if (k.num & 1) {
            heap.q[posi].push_front({k.val, k.dep, 1});
        }
        heap.q[1].push_back({k.val * 2, k.dep + 1, k.num / 2});
    }
    return 0;
}