Problem F: 小 E 与美食

Problem F: 小 E 与美食

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 128 MiB

Description

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

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

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

#include <bits/stdc++.h>
using namespace std;
int n, a[300005];
int cmp(int a, int b) {
    return _____;
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    sort(a + 1, a + n + 1, cmp);
    double ans = 0;
    long long s = 0;
    for (int i = 1; i <= n; i++) {
        s += a[i];
        ans = _________;
    }
    printf("%.8lf", ans);
}


Input

第一行一个正整数 

第二行  个正整数 

数据范围

对于  的数据,

对于  的数据,

对于另  的数据,所有  都相等。

对于  的数据,

Output

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

Sample Input Copy

2
2 1

Sample Output Copy

4.50000000

HINT

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

容易发现两种美食都吃是最优的,舒适度为 

思路:


  • 当选择数量固定时,尽可能选择美味值最大的美食
  • 按照美味值从大到小排序
  • 枚举饱腹感(1到n),计算舒适度,并求解最大值

注意:

在极端数据情况下,满足感的平方可能会超过longlong范围需要转化为double类型进行计算。