破坏挤奶机(Sabotage)

题目描述

农夫约翰的头号敌人保罗决定破坏农民约翰的挤奶设备。挤奶设备排成一行，共 $N$（$3\le N\le 100,000$）台挤奶机，其中第 $i$ 个台挤奶机生产 $M_i$ 单位（$1\le M_i\le 10,000$）的牛奶。

保罗计划切断一段连续的挤奶机，从第 $i$ 台挤奶机到第 $j$ 台挤奶机（$2\le i\le j\le N-1$）。注意，他不希望断开第一台或最后一台挤奶机，因为这将会使他的计划太容易被发现。保罗的目标是让其余机器的平均产奶量最小。保罗计划除去至少 $1$ 台挤奶机。

请计算剩余机器的最小平均产奶量。

输入格式

第 $1$ 行：一个整数 $N$。

第 $2$ 到 $N+1$ 行：第 $i+1$ 行包含一个整数 $M_i$。

输出格式

第 $1$ 行：一个实数，表示平均牛奶产量的最小值，保留三位小数（四舍五入）。

样例输入 #1

5
5
1
7
8
2

样例输出 #1

2.667

数据范围

【样例说明】

移去 $7$ 和 $8$，剩下 $5,1,2$，平均值为 $\dfrac{8}{3}$。

【数据规模和约定】

对于 $30\%$ 的数据，$N\le 1,000$。

对于 $50\%$ 的数据，$N\le 10,000$。

对于 $100\%$ 的数据，$3\le N\le 100,000$，$1\le M_i\le 10,000$。

知识点与难度

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1800。

测试点分布

出处：原题链接