分数: 500 点
问题陈述
Snuke 已经为自己算了明天的运势,得知有 N 可能发生的场景,其中之一明天将以相同的概率发生。的 i第一种情况会让他付出代价 A_i 日元(日本货币)。
在此之后,Snuke 今天决定购买保险。 如果他付钱 x 日元给他的保险公司,他将得到赔偿 \min(A_i,2x) 日元当 A_i 日元丢失。 在这里,他可以选择任何非负数 实数 as x.
Snuke 想要最小化他损失的金额的期望值,即 x+A_i-\min(A_i,2x)。 找到最小的值。
约束
- 1 \leq N \leq 10^5
- 1 \leq A_i \leq 10^9
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N A_1 A_2 \cdots A_N
输出
打印答案。 当你的答案的绝对或相对误差最多为 10^{-6}.
示例输入 1
3 3 1 4
示例输出 1
1.83333333333333333333
最佳选择是 x=1.5。 付款后 1.5 日元,以下三种情况之一将等概率发生:
-
场景 1:输 3 日元并获得补偿 \min(3,2x)=3 日元。毕竟Snuke输了 x+A_1-\min(A_1,2x)=1.5+3-3=1.5 日元。
-
场景 2:输 1 日元并获得补偿 \min(1,2x)=1 日元。毕竟Snuke输了 x+A_2-\min(A_2,2x)=1.5+1-1=1.5 日元。
-
场景 3:输 4 日元并获得补偿 \min(4,2x)=3 日元。毕竟Snuke输了 x+A_3-\min(A_3,2x)=1.5+4-3=2.5 日元。
因此,预期损失金额为 (1.5+1.5+2.5)/3=1.833333\cdots 日元。
示例输入 2
10 866111664 178537096 844917655 218662351 383133839 231371336 353498483 865935868 472381277 579910117
示例输出 2
362925658.10000000000000000000