您是毒瘤？？？
不如去加强荷马史诗（
by AThousandSuns @ 2020-02-01 12:07:57
@[smarthehe](/user/103732) P1020 导弹拦截不也没开新题吗
by LinkCutTree @ 2020-02-01 12:08:11
ok
by WYXkk @ 2020-02-01 12:08:14
Orz
那篇题解不是用桶排序把$log$给去掉了吗，如果加大值域就没法$O(n)$了吧。
~~蒟蒻并不了解什么神奇的算法~~
by Clouder @ 2020-02-01 12:12:56
@[ThereForYou](/user/244485)
可以加强，但没必要。
毕竟这种经典题拿来作堆的模板也不错（
by StudyingFather @ 2020-02-01 12:13:32
事实上哈夫曼编码有两种方式，一种是堆，一种是双队列
双队列的复杂度事实上是 $O(n\log n)$，瓶颈在排序
但是这题的 $a$ 比较小，所以可以堆排做到线性，但不是本题的通用解法
所以实际上这题标算复杂度就当 $O(n\log n)$ 好了，而且如果不是 `vector` 插排的话也不会被平方艹的
所以没有加强的必要
by FZzzz @ 2020-02-01 12:19:49
@[function_of_zero](/user/174045) @[StudyingFather](/user/22030)
好吧。但是还是有加强到 $n\leq 5\times 10^5$ ，$a_i\leq 10^9$ 还是有必要的。
题解里面有用 $O(n^2)$ 插入排序水过的，这样可以卡掉非正解，也可以去掉桶排这个bug，另外还要开LL
by LinkCutTree @ 2020-02-01 12:24:56
> @[ThereForYou](/user/244485) 您是不是应该提供几组数据，毕竟是您要加强 ？
by cstdios @ 2020-02-01 12:33:18
@[cstdios](/user/260980) 貌似管理还没同意加强。如果管理同意，且没空的话，我当然可以造数据
by LinkCutTree @ 2020-02-01 12:40:09
> @[ThereForYou](/user/244485) dalao您为什么要加强数据卡我的STL堆呢 ？
by cstdios @ 2020-02-01 12:41:15