← 返回题目列表

Codeforces · 1557/A

A. Ezzat 和两个子序列

中文机器翻译题面 查看原题

Ezzat 有一个 $$$n$$$ 整数数组(可能是负数)。他想将其拆分为两个非空子序列$$$a$$$和$$$b$$$,使得数组中的每个元素都属于一个子序列,并且$$$f(a) + f(b)$$$的值是最大可能值,其中$$$f(x)$$$是子序列$$$x$$$的平均值。

如果 $$$x$$$ 可以通过删除几个(可能是零个或全部)元素从 $$$y$$$ 获得,则序列 $$$x$$$ 是序列 $$$y$$$ 的子序列。

子序列的平均值是该子序列的数量之和除以子序列的大小。

例如,$$$[1,5,6]$$$的平均值为$$$(1+5+6)/3 = 12/3 = 4$$$,因此$$$f([1,5,6]) = 4$$$。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^3$$$) — 测试用例的数量。每个测试用例由两行组成。

第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 10^5$$$)。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$)。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$3\cdot10^5$$$。

输出

对于每个测试用例,打印一个值 - Ezzat 可以实现的最大值。

如果您的答案的绝对或相对误差不超过 $$$10^{-6}$$$,则视为正确。

正式来说,让您的答案为 $$$a$$$,陪审团的答案为 $$$b$$$。当且仅当 $$$\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-6}$$$ 时,您的答案才会被接受。

示例

输入 #1

4
3
3 1 2
3
-7 -6 -6
3
2 2 2
4
17 3 5 -3

输出 #1

4.500000000
-12.500000000
4.000000000
18.666666667

注意

在第一个测试用例中,数组是 $$$[3, 1, 2]$$$。这些是分割该数组的所有可能方法:

- $$$a = [3]$$$,$$$b = [1,2]$$$,因此 $$$f(a) + f(b) = 3 + 1.5 = 4.5$$$ 的值。
- $$$a = [3,1]$$$,$$$b = [2]$$$,因此 $$$f(a) + f(b) = 2 + 2 = 4$$$ 的值。
- $$$a = [3,2]$$$,$$$b = [1]$$$,因此 $$$f(a) + f(b) = 2.5 + 1 = 3.5$$$ 的值。

在第二个测试用例中,数组为 $$$[-7, -6, -6]$$$。这些是分割该数组的所有可能方法:

- $$$a = [-7]$$$,$$$b = [-6,-6]$$$,因此 $$$f(a) + f(b) = (-7) + (-6) = -13$$$ 的值。
- $$$a = [-7,-6]$$$,$$$b = [-6]$$$,因此 $$$f(a) + f(b) = (-6.5) + (-6) = -12.5$$$ 的值。