Average and Median

题目描述

我们有 $N$ 张卡片。第 $i$ 张卡片 $(1 \leq i \leq N)$ 上写着一个整数 $A_i$。 Takahashi 将从中选择任意张卡片。但是，对于每个 $i$ $(1 \leq i \leq N - 1)$，第 $i$ 张和第 $(i+1)$ 张卡片中至少有一张必须被选择。 求下列数值。

被选择的卡片上所写整数的最大可能平均值 被选择的卡片上所写整数的最大可能中位数

这里，$n$ 个整数的中位数定义为它们中第 $\lceil \frac{n}{2} \rceil$ 小的数，其中 $\lceil x \rceil$ 是不小于 $x$ 的最小整数。

输入格式

输入按照下面的格式从标准输入给出： $N$ $A_1$ $\ldots$ $A_N$

输出格式

输出两行。第一行和第二行分别应包含被选择的卡片上所写整数的最大可能平均值和最大可能中位数。 对于平均值，当你的输出与精确答案的相对或绝对误差不超过 $10^{-3}$ 时，将被视为正确。

6
2 1 2 1 1 10

4
2

7
3 1 4 1 5 9 2

5.250000000
4

提示

$2 \leq N \leq 10^5$ $1 \leq A_i \leq 10^{9}$ 输入中的所有数值都是整数。选择第 $2$、$4$、$6$ 张卡片使得所写整数的平均值为 $\frac{12}{3} = 4$，这是可能的最大值。 选择第 $1$、$3$、$5$、$6$ 张卡片使得所写整数的中位数为 $2$，这是可能的最大值。
对于平均值，你的输出可以包含一定的误差：例如，输出 $5.2491$ 仍将被视为正确。然而对于中位数，必须打印精确值。

标签: AtCoder|abc236E

来源

AtCoder|abc236E