← 返回题目列表

AtCoder · relay2_j

J. 冷漠

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

分数: 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…