A83465.弄丢作业

普及/提高-

官方

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

在一次批改作业的事故中,小牛把前 kk 次作业弄丢了(k1k \ge 1)。剩下的作业中,老师又决定去掉其中最低的一次分数后再计算平均分。
对每个可行的 kk(只要去掉前 kk 份后还剩至少两份作业,才有平均分可算),记对应的平均分为该 kk 的评价值。
你的任务是:找出所有能使该评价值达到最大值的 kk,并按从小到大的顺序输出。

输入格式

第一行一个整数 NN,表示作业次数。

第二行包含 NN 个整数 a1,a2,,aNa_1,a_2,\dots,a_N,表示每次作业的分数。

输出格式

输出若干行:把所有使平均值最大的 kk 值按从小到大各占一行输出。

输入输出样例

  • 输入#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=1k=1:考虑 [1,4,1,5][1,4,1,5],去掉最小的 11 后,平均值为 1+4+1+513=1033.33\displaystyle \dfrac{1+4+1+5-1}{3}=\dfrac{10}{3}\approx 3.33

k=2k=2:考虑 [4,1,5][4,1,5],去掉最小的 11 后,平均值为 4+1+512=4.5\displaystyle \dfrac{4+1+5-1}{2}=4.5

k=3k=3:考虑 [1,5][1,5],去掉最小的 11 后,平均值为 1+511=5\displaystyle \dfrac{1+5-1}{1}=5
最大值出现在 k=3k=3,因此输出 3。

对于样例二:

对于 k=2,3,4,5,6k=2,3,4,5,6,后缀都只包含若干个 1010,或带着唯一的 00;删去最小值后,剩下都是 1010,因此平均值恒为 1010

k=1k=1 时,后缀里有两个 00,删去一个 00 仍有一个 00 留下,平均值降为小于 1010,因此不最优。

于是最优的 kk 有多解:2,3,4,5,62,3,4,5,6

首页