首页 > 代码库 > 203. Hyperhuffman

203. Hyperhuffman

2024-07-16 21:01:56   221人阅读

\(O(nlogn)\)可能会超时，最优二叉树有\(O(n)\)的做法，当年合并果子全机房就我最快，哈哈。。

开两个队列，一个存放未合并的节点，一个存放合并之后的子树，每次取最小时只需考虑这两个队列中的最小值即可，可以证明在队列内的元素单调。

notice: 输入数据已经排好序了， Characters are given from most rare to most frequent 。

 

 1 #include <bits/stdc++.h> 2 #define rep(_i, _j) for(int _i = 1; _i <= _j; ++_i) 3 typedef long long LL; 4 const LL inf = 0x3f3f3f3f3f3f3f3f; 5 typedef double DB; 6 using namespace std; 7  8 const int maxn = 500000 + 10; 9 int n;10 LL que[2][maxn];11 int head[2], tail[2];12 13 #define val(k) (head[k] > tail[k] ? inf : que[k][head[k]])14 15 LL min_val() {16     int d = val(1) < val(0);17     return que[d][head[d]++];18 }19 20 int main() {21 #ifndef ONLINE_JUDGE22     freopen("data.in", "r", stdin); freopen("data.out", "w", stdout);23 #endif24 25     scanf("%d", &n);26     head[0] = head[1] = 0, tail[0] = tail[1] = -1;27     for(int i = 1; i <= n; ++i) {28         scanf("%lld", &que[0][++tail[0]]);29     }30     LL ans = 0;31     for(int i = 1; i < n; ++i) {32         LL t = min_val() + min_val();33         que[1][++tail[1]] = t;34         ans += t;35     }36     printf("%lld\n", ans);37 38     return 0;39 }
View Code

 


联系
我们