|
Лимит времени 4000/7000/7000/7000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
Thailand Informatics Olympiads.
Сложность Бета
Minimax Sum
You are given a sequence of real numbers x1, x2, ..., xn such that n is even.
Design and implement a program to partition the input into n/2 pairs in the following way.
For each pair, we compute the sum of its members. The program should find the partition that
minimizes the maximum sum.
The problem can be solved with this algorithm:
- First sort the list
- Then pair the numbers until the half of the list, in this way
- The first item with nth item
- The second item with (n-1)th item
- The third item with (n-2)th item
- etc.
- Calculate the sum of every pair pair
- Check if they are greater than maxSum
Input specification
You will be first given an integer number (n) which is the number
of inputs, where n is even and 2 ≤ n ≤ 5000. The next line
contains n comma separated integer numbers.
Output specification
Show one integer number which is the miniMax sum.
| |
|
Sample Input:
6
25, 10, 5, 20, 3, 24,
|
Sample Output:
30
|
|
Output Explanation :
| Partitioning 1 |
25 + 10 = 35
5 + 20 = 25
3 + 24 = 27
The maximum sum of the above partition is 35. |
| Partitioning 2 |
25 + 3 = 28
10 + 20 = 30
5 + 24 = 29
The maximum sum of the above partition is 30. |
As in the partitioning strategy 2, you need to find the smallest max sum.
The other partition that the maximum sum is not minimized.
| |
|
Sample Input II:
10
7, 23, 26, 30, 39, 43, 61, 63, 78, 81,
|
Sample Output II:
101
|
|
Для отправки решений необходимо выполнить вход.
|