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

2039_最优合并问题

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

摘要:

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

Pro.ID

2039

Title

最优合并问题

Title链接

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

AC

Submit

110

Ratio

46.36%

时间&空间限制

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

描述

给定k个排好序的序列S₁ , S₂ , ... , S_k, 用二路合并算法将这k个序列合并成一个序列。假设所采用的二路合并算法合并2个长度分别为m和n的序列需要m+n-1次比较。

设计一个算法确定合并这个序列的最优合并顺序，使所需的总比较次数最少。

为了进行比较，还需要确定合并这个序列的最差合并顺序，使所需的总比较次数最多。

对于给定的k个待合并序列，计算最多比较次数和最少比较次数合并方案。

输入

输入第一行是一个正整数k，表示有k个待合并序列。接下来的一行有k个正整数，表示k个待合并序列的长度。

输出

Description

设计一个算法确定合并这个序列的最优合并顺序，使所需的总比较次数最少。

为了进行比较，还需要确定合并这个序列的最差合并顺序，使所需的总比较次数最多。

对于给定的k个待合并序列，计算最多比较次数和最少比较次数合并方案。

Input

输入第一行是一个正整数k，表示有k个待合并序列。接下来的一行有k个正整数，表示k个待合并序列的长度。

Output

输出最多比较次数和最少比较次数。

Sample Input

4
5 12 11 2

Sample Output

78 52

Author

John

样例输入