分数: 100 点
问题陈述
我们有 2N 盆栽。的市场价格 i第锅 (1 ≤ i ≤ 2N) is p_i 日元(日本的货币)。
现在,你和腊肠犬伦伦轮流拿一盆。你先走,我们继续,直到所有的锅都被你或伦伦拿走。由于伦伦不知道各盆的市场价格,她总是会以等概率从剩余的盆中随机选择一盆。你知道伦伦的这个行为,还有罐子的市场价格。
令您拿走的底池的市场价格总和为 S 日元。您的目标是最大化预期价值 S。求出期望值 S 当采用最优策略时。
约束
- 1 ≤ N ≤ 10^5
- 1 ≤ p_i ≤ 2 × 10^5
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N
p_1
:
p_{2N}
输出
打印期望值 S 当策略的期望值最大化时 S 被采用。如果法官输出的绝对或相对误差最多为,则输出被认为是正确的 10^{-9}.
示例输入 1
1 150000 108
示例输出 1
150000.0
当然,你应该选择 150000 日元锅。
示例输入 2
2 50000 50000 100000 100000
示例输出 2
183333.3333333333
首先,您将采取其中之一 100000 日元盆。 100000 如果伦伦下回合没有拿走日元罐,有概率成为你的 2/3。如果被采用,您将不得不接受 50000 日元锅。因此,期望值 S 当采用最优策略时 2/3 × (100000 + 100000) + 1/3 × (100000 + 50000) = 183333.3333…