分数: 500 点
问题陈述
我们有 N 卡。的 i第一张卡 (1 \leq i \leq N) 有一个整数 A_i 。
高桥将从这些卡片中选择任意数量的卡片。然而,对于每个 i (1 \leq i \leq N - 1),至少其中之一 必须选择第 i-th 和 自记录开始以来,第 (i+1)张牌。
找到以下值。
- 所选卡片上写入的整数的最大可能平均值
- 所选卡片上写入的整数的最大可能中位数
这里,中位数 n 整数被定义为 \lceil \frac{n}{2} \rceil- 其中最小的,其中 \lceil x \rceil 是不小于的最小整数 x.
约束
- 2 \leq N \leq 10^5
- 1 \leq A_i \leq 10^{9}
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N A_1 \ldots A_N
输出
打印两行。第一行和第二行应分别包含所选卡片上写入的整数的最大可能平均值和最大可能中位数。 对于平均值,当您的输出与确切答案的相对或绝对误差最多为 10^{-3}.
示例输入 1
6 2 1 2 1 1 10
示例输出 1
4 2
选择 2-nd, 4-th,以及 6第张卡计算写入整数的平均值 \frac{12}{3} = 4,这是可能的最大值。
选择 1-st, 3-rd, 5-th,以及 6第张牌得出写入整数的中位数 2,这是可能的最大值。
示例输入 2
7 3 1 4 1 5 9 2
示例输出 2
5.250000000 4
对于平均值,您的输出可能包含一定程度的错误:例如,输出 5.2491 仍然被认为是正确的。然而,对于中位数,必须打印准确的值。