Description

追逐影子的人，自己就是影子。 ——荷馬

Allison 最近迷上了文學(xué)。她喜歡在一個(gè)慵懶的午后，細(xì)細(xì)地品上一杯卡布奇諾，靜靜地閱讀她愛(ài)不釋手的《荷馬史詩(shī)》。但是由《奧德賽》和《伊利亞特》組成的鴻篇巨制《荷馬史詩(shī)》實(shí)在是太長(zhǎng)了，Allison 想通過(guò)一種編碼方式使得它變得短一些。 一部《荷馬史詩(shī)》中有 n 種不同的單詞，從 1 到 n 進(jìn)行編號(hào)。其中第 i 種單詞出現(xiàn)的總次數(shù)為 wi。Allison 想要用 k 進(jìn)制串 si 來(lái)替換第 i 種單詞，使得其滿足如下要求: 對(duì)于任意的 1≤i,j≤n，i≠j，都有：si 不是 sj 的前綴。 現(xiàn)在 Allison 想要知道，如何選擇 si，才能使替換以后得到的新的《荷馬史詩(shī)》長(zhǎng)度最小。在確保總長(zhǎng)度最小的情況下，Allison 還想知道最長(zhǎng)的 si 的最短長(zhǎng)度是多少？ 一個(gè)字符串被稱為 k 進(jìn)制字符串，當(dāng)且僅當(dāng)它的每個(gè)字符是 0 到 k?1 之間（包括 0 和 k?1）的整數(shù)。 字符串 Str1 被稱為字符串 Str2 的前綴，當(dāng)且僅當(dāng)：存在 1≤t≤m，使得 Str1=Str2[1..t]。其中，m 是字符串 Str2 的長(zhǎng)度，Str2[1..t] 表示 Str2 的前 t 個(gè)字符組成的字符串。

Input

輸入文件的第 1 行包含 2 個(gè)正整數(shù) n,k，中間用單個(gè)空格隔開(kāi)，表示共有 n 種單詞，需要使用 k 進(jìn)制字符串進(jìn)行替換。

接下來(lái) n 行，第 i+1 行包含 1 個(gè)非負(fù)整數(shù) wi，表示第 i 種單詞的出現(xiàn)次數(shù)。

Output

輸出文件包括 2 行。

第 1 行輸出 1 個(gè)整數(shù)，為《荷馬史詩(shī)》經(jīng)過(guò)重新編碼以后的最短長(zhǎng)度。 第 2 行輸出 1 個(gè)整數(shù)，為保證最短總長(zhǎng)度的情況下，最長(zhǎng)字符串 si 的最短長(zhǎng)度。

Sample Input

4 2
1
1
2
2

Sample Output

12
2

HINT

用 X(k) 表示 X 是以 k 進(jìn)制表示的字符串。 一種最優(yōu)方案：令 00(2) 替換第 1 種單詞，01(2) 替換第 2 種單詞，10(2) 替換第 3 種單詞，11(2) 替換第 4 種單詞。在這種方案下，編碼以后的最短長(zhǎng)度為： 1×2+1×2+2×2+2×2=12 最長(zhǎng)字符串 si 的長(zhǎng)度為 2。 一種非最優(yōu)方案：令 000(2) 替換第 1 種單詞，001(2) 替換第 2 種單詞，01(2) 替換第 3 種單詞，1(2) 替換第 4 種單詞。在這種方案下，編碼以后的最短長(zhǎng)度為： 1×3+1×3+2×2+2×1=12 最長(zhǎng)字符串 si 的長(zhǎng)度為 3。與最優(yōu)方案相比，文章的長(zhǎng)度相同，但是最長(zhǎng)字符串的長(zhǎng)度更長(zhǎng)一些。 對(duì)于所有數(shù)據(jù)，保證 2≤n≤100000，2≤k≤9。 選手請(qǐng)注意使用 64 位整數(shù)進(jìn)行輸入輸出、存儲(chǔ)和計(jì)算。

題解

因?yàn)椴荒苡邢嗤熬Y，顯然就是$Huffman$，那么就是$k$叉$Huffman$樹(shù)合并。

 1 //It is made by Awson on 2017.11.4
 2 #include <map>
 3 #include <set>
 4 #include <cmath>
 5 #include <ctime>
 6 #include <queue>
 7 #include <stack>
 8 #include <cstdio>
 9 #include <string>
10 #include <vector>
11 #include <cstdlib>
12 #include <cstring>
13 #include <iostream>
14 #include <algorithm>
15 #define LL long long
16 #define Max(a, b) ((a) > (b) ? (a) : (b))
17 #define Min(a, b) ((a) < (b) ? (a) : (b))
18 #define Abs(a) ((a) < 0 ? (-(a)) : (a))
19 using namespace std;
20 const int N = 100000;
21 
22 int n, k;
23 struct node {
24     LL h, v;
25     node() {
26     }
27     node(LL _h, LL _v) {
28     h = _h, v = _v;
29     }
30     bool operator < (const node &b) const {
31     return v == b.v ? h > b.h : v > b.v;
32     } 
33 }a;
34 priority_queue<node>Q;
35 
36 void work() {
37     scanf("%d%d", &n, &k);
38     for (int i = 1; i <= n; i++) {
39     scanf("%lld", &a.v); a.h = 0;
40     Q.push(a);
41     }
42     int rest = 0;
43     if ((n-1)%(k-1)) rest = k-1-((n-1)%(k-1));
44     for (int i = 1; i <= rest; i++) Q.push(node(0, 0));
45     LL ans = 0;
46     while (Q.size() != 1) {
47     LL tmp = 0, height = 0;
48     for (int i = 1; i <= k; i++) {
49         tmp += Q.top().v, height = Max(height, Q.top().h); Q.pop();
50     }
51     ans += tmp;
52     Q.push(node(height+1, tmp));
53     }
54     printf("%lld\n%lld\n", ans, Q.top().h);
55 }
56 int main() {
57     work();
58     return 0;
59 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/NaVi-Awson/p/7782361.html

總結(jié)

以上是生活随笔為你收集整理的[NOI 2015]荷马史诗的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。