同和创作矩阵 › ›博文归档› 技术博文归档 › 查看内容

2056_多元Huffman编码问题

2022-5-16 18:18| 发布者: Hocassian| 查看: 59| 评论: 0|原作者: 肇庆学院ACM合集

摘要:

C:\Users\Administrator\Downloads\2019-10-12-10-14-3-89504283513100-Problem List-采集的数据-后羿采集器.html

Pro.ID

2056

Title

多元Huffman编码问题

Title链接

http://10.20.2.8/oj/exercise/problem?problem_id=2056

AC

Submit

Ratio

0.00%

时间&空间限制

Time Limit: 1000/500 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)

描述

在一个操场的四周摆放着n堆石子。现要将石子有次序地合并成一堆。规定每次至少选2堆、最多选k堆石子合并成新的一堆，合并的费用为新的一堆的石子数。对于给定n堆石子，计算合并成一堆的最大总费用和最小总费用。

输入

输入的第一行有两个正整数n和k，表示有n堆石子，每次至少选两堆、最多选k堆石子合并。 5 ≤ n ≤ 100000 , 2 ≤ k ≤ 6688

第二行有n个数，分别表示每堆石子的个数。

输出

Description

Input

输入的第一行有两个正整数n和k，表示有n堆石子，每次至少选两堆、最多选k堆石子合并。 5 ≤ n ≤ 100000 , 2 ≤ k ≤ 6688

第二行有n个数，分别表示每堆石子的个数。

Output

输出最大总费用和最小总费用

Sample Input

7 3
45 13 12 16 9 5 22

Sample Output

593 199

Author

John

样例输入