Problem F: 小 E 与美食
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
Sample Input Copy
2
2 1
Sample Output Copy
4.50000000
HINT
建议输出至少 位有效数字。
容易发现两种美食都吃是最优的,舒适度为 。
思路:
- 当选择数量固定时,尽可能选择美味值最大的美食
- 按照美味值从大到小排序
- 枚举饱腹感(1到n),计算舒适度,并求解最大值
注意:
在极端数据情况下,满足感的平方可能会超过longlong范围需要转化为double类型进行计算。