AT_abc236_e [ABC236E] Average and Median

题目描述

有 $N$ 张卡片，第 $i$ 张卡片上写有整数 $A_i$。

高桥君可以从这些卡片中任选若干张。但对于每个 $i\ (1 \leq i \leq N-1)$，必须选择第 $i$ 张卡片和第 $i+1$ 张卡片中的至少一张。

请你求出以下两个值：

• 作为所选卡片上整数的平均值可能取得的最大值。
• 作为所选卡片上整数的中位数可能取得的最大值。

其中，$n$ 个整数的中位数定义为按从小到大排序后第 $\lceil \frac{n}{2} \rceil$ 个数。这里，$\lceil x \rceil$ 表示大于等于 $x$ 的最小整数。

输入格式

输入从标准输入中给出，格式如下：

$N$ $A_1$ $A_2$ $\ldots$ $A_N$

输出格式

输出共两行。第一行输出所选卡片上整数的平均值可能取得的最大值，第二行输出所选卡片上整数的中位数可能取得的最大值。对于平均值的输出，只要与正确答案的相对误差或绝对误差不超过 $10^{-3}$ 即可视为正确。中位数必须输出精确值。

输入输出样例 #1

输入 #1

6
2 1 2 1 1 10

输出 #1

4
2

输入输出样例 #2

输入 #2

7
3 1 4 1 5 9 2

输出 #2

5.250000000
4

说明/提示

限制条件

• $2 \leq N \leq 10^5$
• $1 \leq A_i \leq 10^9$
• 输入均为整数。

样例解释 1

选择第 2、4、6 张卡片时，所选整数的平均值为 $\frac{12}{3} = 4$，这是最大值。选择第 1、3、5、6 张卡片时，所选整数的中位数为 $2$，这是最大值。

样例解释 2

对于平均值的输出，允许有一定误差，例如输出 $5.2491$ 也会被判为正确。但中位数必须输出精确值。

由 ChatGPT 4.1 翻译