PROGRAMMING:Optimal merger problem
Title Source: algorithm design and analysis by Wang Xiaodong
Given K ordered sequences, the K sequences are combined into one sequence by two-way merging algorithm.
Suppose that the two-way merging algorithm needs m + n-1 comparison to merge two sequences of length m and N respectively. Trial design
An algorithm is used to determine the optimal order of merging the sequence to minimize the total number of comparisons.
In order to compare, it is also necessary to determine the worst merging order of the merging sequence, so that the total number of comparisons required is the most.
###Input format:
The first line has a positive integer k, which means that there are k sequences to be merged.
The second line has k positive integers, which represent the length of K sequences to be merged.
###Output format:
Output the maximum number of comparisons and the minimum number of comparisons.
###Input example:
Here is a set of inputs. For example:
```in
four
5 12 11 2
```
###Output example:
The corresponding output is given here. For example:
```out
78 52
```
answer：If there is no answer, please comment
Given K ordered sequences, the K sequences are combined into one sequence by two-way merging algorithm.
Suppose that the two-way merging algorithm needs m + n-1 comparison to merge two sequences of length m and N respectively. Trial design
An algorithm is used to determine the optimal order of merging the sequence to minimize the total number of comparisons.
In order to compare, it is also necessary to determine the worst merging order of the merging sequence, so that the total number of comparisons required is the most.
###Input format:
The first line has a positive integer k, which means that there are k sequences to be merged.
The second line has k positive integers, which represent the length of K sequences to be merged.
###Output format:
Output the maximum number of comparisons and the minimum number of comparisons.
###Input example:
Here is a set of inputs. For example:
```in
four
5 12 11 2
```
###Output example:
The corresponding output is given here. For example:
```out
78 52
```
answer：If there is no answer, please comment