#AT0013. 小 E 与美食

    ID: 464 远端评测题 1000ms 500MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>算法基础贪心Special Judge洛谷月赛

小 E 与美食

题目背景

小 E 是一个热爱美食的高中生,但吃的太多会导致他身体不舒服,他想找到一个能让他最舒服的方案,快来帮帮他!

题目描述

小 E 有 nn 种美食可供选择,每种美食只能吃一次,第 ii 种美食有一个美味值 aia_i,吃下一个美味值为 aia_i 的美食可以让小 E 的满足感提升 aia_i

但是小 E 的胃是有极限的,每吃下一个美食,他的饱腹感就会提升 11

小 E 最后的舒适度是他的满足感的平方除以他的饱腹感,你的目标是求出他舒适度能达到的最大值。

输入格式

第一行一个正整数 nn

第二行 nn 个正整数 a1,a2,,ana_1, a_2, \cdots, a_n

输出格式

输出一行一个实数,表示小 E 舒适度的最大值,你的输出与标准答案的相对误差或绝对误差在 10610^{-6} 以内即视为正确。

2
2 1
4.50

提示

提示

建议输出至少 88有效数字。

样例解释

容易发现两种美食都吃是最优的,舒适度为 (2+1)22=4.5\frac{(2+1)^2}{2} = 4.5

数据范围

对于 30%30 \% 的数据,n,ai20n, a_i \le 20

对于 50%50 \% 的数据,n,ai2000n, a_i \le 2000

对于另 15%15 \% 的数据,所有 aia_i 都相等。

对于 100%100 \% 的数据,1n3×1051 \le n \le 3 \times 10^{5}1ai1061 \le a_i \le 10^6