A39215. 炫耀成绩
填空题
困难
知识点
题目描述
炫耀成绩
题目描述
猴帅老师所教班级刚刚进行了一次测试，猴帅老师邀请编程组的黑客老师一起判卷，其实是想秀一秀自己学生成绩。试卷从上到下编号 1 ~ n，猴帅老师对自己学生了如指掌，一下就掌握了他们的实际分数。猴帅老师为了显得不这么刻意，会主动说第 i 个试卷到第 j 个试卷自己判，其中 1 < i <= j < n，即侯帅老师一定不会选择第 1 个试卷和第 n 个试卷，其余交给黑客老师。请帮助猴帅老师分析下，在保证猴帅老师与黑客老师都判卷至少 1 张的情况下，如何选择试卷能让黑客老师所判试卷的平均分最高。最高的平均分为多少？
输入格式
共 2 行
第 1 行，1 个整数 n，代表试卷数量。
第 2 行，n 个整数 a1,a2,……,an，代表每张试卷的实际分数。
输出格式
共 1 行，一个实数，表示最高的平均分，保留三位小数 （四舍五入）。
输入样例 1
5
8 9 12 5 9输出样例 1
9.500【样例 1 说明】
猴帅老师把第 4 张试卷拿走自己批阅。剩下 4 张的平均分是 9.500
【输入样例 2】
6
2 7 3 1 3 5【输出样例 2】
4.667【数据说明】
对于 30%数据：n <= 1000；
对于 100%数据：10 <= n <= 200000，0 <= ai <= 10000，1 < i <= j < n。
参考答案
# include <cstdio>
# include <cstring>
# include <algorithm>
# include <cmath>
# include <iostream>
using namespace std;
const int NR = 2e5 + 10;
int a[NR];
int n;
long long sum;
bool check(int x) {
long long t = 0, ans = 9e18;
for (int i = 2; i <= n - 1; i++) {
if (t < 0) t += a[i] - x; else t = a[i] - x;
ans = min(ans, t);
}
return ans <= sum - 1ll * n * x;
}
int main() {
// freopen("0.in", "r", stdin);
// freopen("0.out", "w", stdout);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
a[i] *= 100000;
sum += a[i];
}
int l = 0, r = 1e9, ans = 1e9;
while (l <= r) {
int m = (l + r) / 2;
if (check(m)) ans = m, l = m + 1; else r = m - 1;
}
printf("%.3f", ans / 100000.0);
return 0;
}
上一题
下一题