A83465.弄丢作业
普及/提高-
官方
通过率:0%
时间限制:1.00s
内存限制:128MB
题目描述
在一次批改作业的事故中,小牛把前 k 次作业弄丢了(k≥1)。剩下的作业中,老师又决定去掉其中最低的一次分数后再计算平均分。
对每个可行的 k(只要去掉前 k 份后还剩至少两份作业,才有平均分可算),记对应的平均分为该 k 的评价值。
你的任务是:找出所有能使该评价值达到最大值的 k,并按从小到大的顺序输出。
输入格式
第一行一个整数 N,表示作业次数。
第二行包含 N 个整数 a1,a2,…,aN,表示每次作业的分数。
输出格式
输出若干行:把所有使平均值最大的 k 值按从小到大各占一行输出。
输入输出样例
输入#1
5 3 1 4 1 5
输出#1
3
输入#2
8 10 0 10 10 10 0 10 10
输出#2
2 3 4 5 6
说明/提示
对于样例一:
k=1:考虑 [1,4,1,5],去掉最小的 1 后,平均值为 31+4+1+5−1=310≈3.33。
k=2:考虑 [4,1,5],去掉最小的 1 后,平均值为 24+1+5−1=4.5。
k=3:考虑 [1,5],去掉最小的 1 后,平均值为 11+5−1=5。
最大值出现在 k=3,因此输出 3。
对于样例二:
对于 k=2,3,4,5,6,后缀都只包含若干个 10,或带着唯一的 0;删去最小值后,剩下都是 10,因此平均值恒为 10。
当 k=1 时,后缀里有两个 0,删去一个 0 仍有一个 0 留下,平均值降为小于 10,因此不最优。
于是最优的 k 有多解:2,3,4,5,6。