#P10889. [2015yali备战noi]code

    ID: 10032 传统题 1000ms 256MiB 尝试: 5 已通过: 1 难度: 9 上传者: 标签>CF2800省选/NOI-Garsia-Wachs 算法FHQ Treap 分裂合并按排名分裂

[2015yali备战noi]code

题目描述

给定有序字母集 χ\chi 中每个字母的出现频率,给每个字母分配一个二进制串作为编码,满足:

  • 任何一个字母的编码都不是另一个字母编码的前缀。
  • 按照字母的原顺序排列,各字母的编码按字典序递增。

编码方案的权重是

$$\sum_{c\in\chi} \operatorname{length}(\operatorname{code}(c))\operatorname{frequency}(c).$$

求满足以上条件的最小权重。

例如,对于依次排列的 A,B,C,DA,B,C,D,编码 000,001,01,10000,001,01,10 同时满足前缀和顺序条件;11,00,10,0111,00,10,01 满足前缀条件;0,00,000,10,00,000,1 满足顺序条件。若频率分别为 5,1,7,35,1,7,3,第一种方案的权重为 3838。

输入格式

第一行一个整数 NN(1≤N≤1000001\le N\le100000),表示字母个数。第二行按顺序给出 NN 个字母的频率,每个频率均为 11 到 10000001000000 之间的整数。

输出格式

输出一个整数,表示最小权重。

样例

4
5 1 3 7
29

样例的一种最优编码为 00,010,011,100,010,011,1,权重为 5⋅2+1⋅3+3⋅3+7⋅1=295\cdot2+1\cdot3+3\cdot3+7\cdot1=29。

原 PDF 题面