F-神奇编码

#include <bits/stdc++.h>
typedef long long ll;

using namespace std;

priority_queue<vector<ll>, vector<vector<ll> >, greater<vector<ll>> > pq;

int main() {
    ll n, k;
    cin>>n;
    for (ll i=1;i<=n;i++) {
        cin>>k;
        pq.push({i, 0, k});
    }
    pair<ll, ll> res;
    bool flag = false;
    while (pq.size()) {
        auto x = pq.top();
        pq.pop();
        if (flag) {
            res.first = res.first + x[0];
            //选取最高的加一才会正确结果
            res.second = max(res.second, x[1])+1;
            pq.push({res.first, res.second, 1});
            x[2]--;
            flag = false;
        }
        if (x[2]>=2) {
            pq.push({x[0]*2, x[1]+1, x[2]/2});
            x[2] %= 2;
        }
        if (x[2]) {
            flag = true;
            res = {x[0], x[1]};
        }
    }
    cout<<res.second<<endl;
    
    return 0;
}

//首先从题目上来说，构造一个哈夫曼树需要贪心的将两个最小的节点进行连接。
//而题目中将相同概率的节点进行了压缩，这就引出了一个方法，由于有相同节点的存在，所以如果节点数量是偶数的时候那必然全部选择最小的相同节点。
//所以在这时候直接针对除以2即可、如果是奇数的话那么就但拎出来一个数，将其变成偶数再直接砍半。
//而现在的问题就是如何维护最小的两个节点，最直接的方式是使用优先队列，但问题的数据卡的很死。由于优先队列里面有log复杂度的存在所以过不了。
//在这时候可以借鉴【NOIP2016 蚯蚓】的解法，使用两个双端队列来一个维护相加后的一个节点，由于哈夫曼树的相加总是越加越大的。所以在尾部进行插入那么头部就是最小的节点。
//一个是原来的节点，一个是合并和的节点。最小值肯定从这两个里面取得。
#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;
const int maxn = 1e5+10;
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;
}
struct node {
    int val;
    int h;
    int num;
    inline bool operator < (const node &o) const {
        if (val!=o.val) 
            return val<o.val;
        return h<o.h;
    }
    inline node operator + (const node &o) const {
        node n;
        n.val = val+o.val;
        n.h = max(h, o.h)+1;
        n.num = 1;
        return n;
    }
};
int b[maxn];
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()) {
//             if (q[0].empty())  {posi = 1; return q[1].front();}
//             else {posi=0; return q[0].front();}
            return q[posi = q[0].empty()].front();
        }
        return q[0].front() < q[1].front() ? (posi = 0, q[0].front())
                                           : (posi = 1, q[1].front());
    }
} hp;

signed main() {
    int n, num = 0;
    n = rd();
    //将所有初始节点放入q[0]队列里面
    for (int i=1;i<=n;i++) {
        b[i] = rd();
        if (b[i])
        hp.q[posi].push_back({i, 0, b[i]});
    }
    //开始构造哈夫曼
    while (!hp.empty()) {
        //弹出第一个最小的
        node x = hp.top();
        hp.q[posi].pop_front();
        //如果只有一个的话
        if (x.num==1) {
            if (hp.empty()) {
                cout<<x.h<<endl;
                return 0;
            }
            //弹出下一个最小的
            node nextx = hp.top();
            hp.q[posi].pop_front();
            nextx.num--;
            if (nextx.num) {
                hp.q[posi].push_front(nextx);
            }
            hp.q[1].push_back(x+nextx);
            continue;
        } 
        //如果是奇数的话
        if (x.num&1) {
            hp.q[posi].push_front({x.val, x.h, 1});
        }
        //如果是偶数的话
        hp.q[1].push_back({x.val*2, x.h+1, x.num/2});
    }
    
    
    return 0;
}