CSP 模拟 · CSP 2020 第一轮（初赛）模拟 第 20 题

（烧作业）某课作业布置了 $N(3\leq N\leq 100000)$ 个题目，第 $i$ 题对应的得分是 $a_i$。作业的总得分的计算方式为去掉作业中得分最小的一个题，剩下其它所有题目得分的平均值。但很不幸小 A 遇到了一场火灾，前 $K(1\leq K\leq N-2)$ 个题目被烧了，无法记录得分。小 A 想知道，$K$ 是多少时，可以得到最高的作业得分？ 作业被烧了前 $K$ 页，这时的得分是从第 $K+1$ 页到最后一页中，去除最小得分后取平均值。

输入第一行是整数 $N$，第二行是 $n$ 个不超过 $10000$ 的非负整数表示 $a_i$。

输出一行，若干个整数表示答案。如果有多个 $K$，请依次升序输出。

``` #include <cstdio> #include <cmath> #define min(a,b) (a<b?a:b) #define MAXN 100002 using namespace std; int n, k[MAXN], cnt = 0; int s[MAXN], minScore, sum; double maxAverage = 0, nowAverage; int main() { scanf("%d", &n); for(int i = 1; i <= n; i++) scanf("%d", &s[i]); minScore = s[n]; ①; for(int i = n - 1; i >= 2; i--) { minScore = min(minScore, s[i]); ②; nowAverage = ③; if(nowAverage > maxAverage) { ④ maxAverage = nowAverage; } else if(fabs(nowAverage - maxAverage) < 1e-6)

（本题为阅读程序 / 完善程序，完整题目与测试数据见平台）

这题本质是前缀和 + 后缀最小值的动态维护。拿到数组后，先算出后缀和与后缀最小值，然后从后往前枚举被烧毁的页数 K，用 O(1) 更新当前剩余部分的总和与最小值，算出平均值比较大小即可。注意浮点误差要用 eps 判断，且题目要求输出所有最优 K，需要记录并倒序输出。

最容易栽跟头的地方有三处：一是忘记去掉最小值再求平均，导致算出的值偏大；二是用 int 做除法没转 double，或者分子分母搞反了；三是遇到多个 K 得到相同最大值时，只记录了一个，漏掉了其他同样优秀的解。另外，因为是从后往前枚举，最优解出现得越靠后（K 越小），在数组里存的位置越靠后，所以最后输出时必须倒序，否则会乱序。

烧作业——从后往前枚举，用前缀和与后缀最小值秒解

1. 题目在考什么

这是一道典型的“枚举 + 后缀最值 + 平均值比较”题。给定 N 个非负整数，前 K 个被烧掉，剩下 N-K 个数中要去掉最小值再求平均。问哪些 K 能让这个平均值最大。数据范围 N 到 10^5，a_i 到 10^4，要求 O(N) 或 O(N log N)。命题人喜欢在这里挖坑：浮点误差、多解输出顺序、分子分母写反、忘记去最小值。