Description

追逐影子的人, 自己就是影子.----荷马

Allison 最近迷上了文学. 她喜欢在一个慵懒的午后, 细细地品上一杯卡布奇诺, 静静地阅读她爱不释手的《荷马史诗》. 但是由《奥德赛》和《伊利亚特》组成的鸿篇巨制 《荷马史诗》实在是太长了, Allison 想通过一种编码方式使得它变得短一些.

一部《荷马史诗》中有 \(n\) 种不同的单词, 从 \(1\) 到 \(n\) 进行编号. 其中第 \(i\) 种单词出现的总次数为 \(w_i\). Allison 想要用 \(k\) 进制串 \(s_i\) 来替换第 \(i\) 种单词, 使得 其满足如下要求:

对于任意的 \(1 \leq i, j \leq n, i \neq j\), 都有:\(s_i\) 不是 \(s_j\) 的前缀.

现在 Allison 想要知道, 如何选择 \(s_i\), 才能使替换以后得到的新的《荷马史诗》长度 最小. 在确保总长度最小的情况下, Allison 还想知道最长的 \(s_i\) 的最短长度是多少?

一个字符串被称为 \(k\) 进制字符串, 当且仅当它的每个字符是 \(0\) 到 \(k - 1\) 之间 (包括 \(0\) 和 \(k - 1\)) 的整数.

字符串 \(Str_1\) 被称为字符串 \(Str_2\) 的前缀, 当且仅当: 存在 \(1 \leq t \leq m\), 使得 \(Str_1 = Str_2[1 \ldots t]\). 其中,\(m\) 是字符串 \(Str_2\) 的长度,\(Str_2[1 \ldots t]\) 表示 \(Str_2\) 的前 \(t\) 个字符组成的字符串.

Input

输入文件的第 \(1\) 行包含 \(2\) 个正整数 \(n, k\), 中间用单个空格隔开, 表示共有 \(n\) 种单词, 需要使用 \(k\) 进制字符串进行替换.

接下来 \(n\) 行, 第 \(i+1\) 行包含 \(1\) 个非负整数 \(w_i\), 表示第 \(i\) 种单词的出现次数.

Output

输出文件包括 \(2\) 行.

第 \(1\) 行输出 \(1\) 个整数, 为《荷马史诗》经过重新编码以后的最短长度.

第 \(2\) 行输出 \(1\) 个整数, 为保证最短总长度的情况下, 最长字符串 \(s_i\) 的最短长度.

Sample Input

4 2
1
1
2
2

Sample Output

12
2

Data Range

对于所有数据, 保证:\(2 \leq n \leq 10^5, 2 \leq k \leq 9\);

选手请注意使用 \(64\) 位整数进行输入输出、存储和计算.

Explanation

如果这道题想到哈夫曼树就可以了, 不然根本做不出来.

或者有类似的想法也行. 毕竟这样合并的次数最少, 代价也最小.

这让我想到了 Minecraft 的附魔机制, 最好的办法是两两附魔然后合并, 而不是线性地一股脑全部扔到附魔台上去.

具体实现方法也不是很不明确, 另外注意整除的问题.

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <queue>

using namespace std;
typedef long long lli;

struct obj { lli w; int l;
    obj(lli _, int __) { w = _, l = __; } };
bool operator < (obj a, obj b) {
    return a.w != b.w ? a.w > b.w : a.l > b.l; }

int n, k;
priority_queue<obj> pq;

int main(int argc, char** argv)
{
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) {
        lli x; scanf("%lld", &x);
        pq.push(obj(x, 1));
    }
    int m = n;
    // Maintain divisor intactness
    if ((n-1) % (k-1) > 0)
        m += (k-1) - (n-1) % (k-1);
    for (int i = n + 1; i <= m; i++)
        pq.push(obj(0, 1));
    // Emulating selection
    lli res = 0;
    while (m > 1) {
        lli s1 = 0; int s2 = 0;
        for (int i = 1; i <= k; i++) {
            obj s = pq.top(); pq.pop();
            s1 += s.w; s2 = max(s2, s.l);
        }
        res += s1; m -= k - 1;
        pq.push(obj(s1, s2 + 1));
    }
    printf("%lld\n%d\n", res, pq.top().l - 1);
    return 0;
}