题目描述

$2N$ 個の壺があります。このうち $i$ 個目の壺 $(1\ <\ =\ i\ <\ =\ 2N)$ の市場価格は $p_i$ 円です。

これから、あなたとダックスフンドのルンルンは交互に壺を一つずつ取っていきます。あなたから始めて、すべての壺があなたかルンルンに取られるまで続けます。ルンルンは壺の市場価格がわからないので、毎回、残っている壺の中から無作為に等確率で一つを選びます。あなたはこのルンルンの行動と、壺の市場価格を知っています。

あなたの目的は、取る壺の市場価格の合計を $S$ 円としたとき、$S$ の期待値を最大化することです。最適な戦略を取ったときの $S$ の期待値を求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $p_1$ $:$ $p_{2N}$

输出格式

$S$ の期待値を最大化する戦略を取ったときの $S$ の期待値を出力せよ。出力は、ジャッジの出力からの絶対誤差または相対誤差が $10^{-9}$ 以下であれば正答とみなされる。

题目大意

一共有2N个罐子，每个罐子都有不同的价值

你和另一个人轮流选择罐子（你先手），你可以任意选择罐子，另一个人将随机选取

问你所得最大价值的期望

1
150000
108

150000.0

2
50000
50000
100000
100000

183333.3333333333

提示

制約

• $1\ <\ =\ N\ <\ =\ 10^5$
• $1\ <\ =\ p_i\ <\ =\ 2\ ×\ 10^5$
• 入力値はすべて整数である。

Sample Explanation 1

当然、$15$ 万円の壺を選ぶべきです。

Sample Explanation 2

あなたはまず、$10$ 万円の壺のうち一つを取ります。もう一つの $10$ 万円の壺は、次のルンルンの番で取られなければ手に入り、その確率は $2/3$ です。もしその壺を取られてしまった場合は、$5$ 万円の壺で我慢することになります。以上から、最適な戦略を取ったときの $S$ の期待値は $ 2/3\ ×\ (100000\ +\ 100000)\ +\ 1/3\ ×\ (100000\ +\ 50000)\ =\ 183333.3333… $ となります。