308683: CF1557A. Ezzat and Two Subsequences
Memory Limit:256 MB
Time Limit:1 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Ezzat and Two Subsequences
题意翻译
**【题目描述】** Ezzat 有一个长度为 $n$ 的数组,他想将这个数组分成非空的数组 $a$ 和 $b$,使得 $f(a)+f(b)$ 最大,其中 $f(x)$ 表示 数组 $x$ 的平均值。 比如 $f([1,5,6])=\dfrac{1+5+6}{3}=4$。 **【输入格式】** 第一行一个正整数 $t$,表示有 $t$ 组数据。 对于每组数据,第一行一个正整数 $n$,第二行有 $n$ 个正整数 $a_1,a_2\ldots,a_n$。 **【输出格式】** 对于每组数据,每一行输出满足 Ezzat 的数组 $a$ 和 $b$ 的平均数之和。 记你的答案为 $a$,标准答案为 $b$ ,如果 $\dfrac{|a-b|}{\max(1,|b|)}\le10^{-6}$,那你的的答案就是正确的。 **【数据范围】** $1\le t\le10^3$,$2\le n\le10^5$,$-10^9\le a_i\le10^9$,$\sum n\le3\times10^5$。 translated by @[lfxxx](https://www.luogu.com.cn/user/478461)题目描述
Ezzat has an array of $ n $ integers (maybe negative). He wants to split it into two non-empty subsequences $ a $ and $ b $ , such that every element from the array belongs to exactly one subsequence, and the value of $ f(a) + f(b) $ is the maximum possible value, where $ f(x) $ is the average of the subsequence $ x $ . A sequence $ x $ is a subsequence of a sequence $ y $ if $ x $ can be obtained from $ y $ by deletion of several (possibly, zero or all) elements. The average of a subsequence is the sum of the numbers of this subsequence divided by the size of the subsequence. For example, the average of $ [1,5,6] $ is $ (1+5+6)/3 = 12/3 = 4 $ , so $ f([1,5,6]) = 4 $ .输入输出格式
输入格式
The first line contains a single integer $ t $ ( $ 1 \le t \le 10^3 $ )— the number of test cases. Each test case consists of two lines. The first line contains a single integer $ n $ ( $ 2 \le n \le 10^5 $ ). The second line contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ -10^9 \le a_i \le 10^9 $ ). It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 3\cdot10^5 $ .
输出格式
For each test case, print a single value — the maximum value that Ezzat can achieve. Your answer is considered correct if its absolute or relative error does not exceed $ 10^{-6} $ . Formally, let your answer be $ a $ , and the jury's answer be $ b $ . Your answer is accepted if and only if $ \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