首页 > 代码库 > 203. Hyperhuffman
203. Hyperhuffman
\(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 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。