[ARC122B] Insurance

题面翻译

题目描述

Snuke预测了他明天的命运，并且得知有 $N$ 种情况，每一种情况等概率发生。第 $i$ 种情况将花费他 $A_i$ 日元。

于是，Snuke决定购买保险。如果他向保险公司支付 $x$ 日元，当 $A_i$ 日元丢失时，他将得到 $min(A_i,2x)$ 日元的补偿。在这里，$x$ 可以是任意非负实数。

Snuke希望让他损失金额的期望值尽量小，即最小化 $x+A_i−\min(A_i,2x)$ 。找到这个最小值。

数据范围

• $1 \le N \le 10^5$
• $1 \le A_i \le 10^9$
• 所有输入都是整数。

Translated By @joe_zxq .

题目描述

すぬけくんは明日の運勢を占いました． その結果，$N$ 個のシナリオのうちどれか一つが等確率で発生し，そのうち $i$ 番目のシナリオでは $A_i$ 円を失うことを知りました．

そこですぬけくんは，今日保険に入ることにしました． 保険会社に $x$ 円を支払ったとすると，$A_i$ 円を失った場合には $\min(A_i,2x)$ 円が補填されます． ここで，$x$ として任意の非負実数を選ぶことができます．

すぬけくんは，最終的に自分が失う金額（$=x+A_i-\min(A_i,2x)$）の期待値を最小化したいです． この最小値を求めてください．

输入格式

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

$N$ $A_1$ $A_2$ $\cdots$ $A_N$

输出格式

答えを出力せよ． 絶対誤差または相対誤差が $10^{-6}$ 以下ならば，正解と判定される．

样例 #1

样例输入 #1

3
3 1 4

样例输出 #1

1.83333333333333333333

样例 #2

样例输入 #2

10
866111664 178537096 844917655 218662351 383133839 231371336 353498483 865935868 472381277 579910117

样例输出 #2

362925658.10000000000000000000

提示

制約

• $1\ \leq\ N\ \leq\ 10^5$
• $1\ \leq\ A_i\ \leq\ 10^9$
• 入力される値はすべて整数である

Sample Explanation 1

$x=1.5$ とするのが最適です． $1.5$ 円支払ったあと，以下の $3$ つのシナリオが等確率で起こります． - シナリオ $1$: $3$ 円失ったあと，$\min(3,2x)=3$ 円が補填される． 最終的にすぬけくんが失う金額は，$x+A_1-\min(A_1,2x)=1.5+3-3=1.5$ 円である． - シナリオ $2$: $1$ 円失ったあと，$\min(1,2x)=1$ 円が補填される． 最終的にすぬけくんが失う金額は，$x+A_2-\min(A_2,2x)=1.5+1-1=1.5$ 円である． - シナリオ $3$: $4$ 円失ったあと，$\min(4,2x)=3$ 円が補填される． 最終的にすぬけくんが失う金額は，$x+A_3-\min(A_3,2x)=1.5+4-3=2.5$ 円である． よって，失う金額の期待値は，$(1.5+1.5+2.5)/3=1.833333\cdots$ です．