相信大家前面两题都是用huffman code queue实现的吧。

也就是说维护一个小根堆(heap)，每次取堆头的两个元素出来相加作为一次操作，然后扔进堆中继续，直到做了n-1次为止（合并完成）。

这样的复杂度显然是O(nlogn)，对于前面两题足够了，对于本题不优秀，所以我们需要深挖题目性质。

观察到，每次操作过后出现的这个数，他一定是单调递增的。

也就是说，每次操作的代价一定是单调递增的。

我们考虑维护两个队列，第一个队列存的是原始的数（从小到大排序），第二个队列存储合并后的数。

那么只要我们一直从第二个队列的队尾插入，那么第二个队列中的元素也是单调递增的，和第一个队列相同。

那么每次我们取两个队列的队头、以及正数第二个元素进行比较，取最小的相加即可。

记得判断一下边界情况，比如队列为空等等。

然后这样操作部分的复杂度就是O(n)了，可以通过99%的数据。

对于1%的数据，我们把sort改为基数排序(radix sort)就可以了。

复杂度O(n)。