分数: 366 分
问题陈述
高桥正在分析气象数据。
有 N 观测站排列成一排,每个观测站 i (1 \leq i \leq N) 已记录温度 F_i 当天。高桥希望对数据进行平滑处理,以使最高温度值不那么突出。
在平滑过程中,他选择一个整数 l (1 \leq l \leq N - K + 1) 这样 K 连续站均落入观测站范围内,并分组站 l, l+1, \ldots, l+K-1 在一起。组内所有站点温度同时替换为组内算术平均值 \displaystyle\frac{F_l + F_{l+1} + \cdots + F_{l+K-1}}{K}。未纳入该组的站点温度保持不变。该操作仅执行一次(不允许选择不执行该操作)。
让 F'_1, F'_2, \ldots, F'_N 为操作后各站的温度。也就是说,对于车站 i 包含在组中 (l \leq i \leq l+K-1), \displaystyle F'_i = \frac{F_l + F_{l+1} + \cdots + F_{l+K-1}}{K},以及所有其他电台 i, F'_i = F_i。此处,均值完全按照实数计算,不进行截断或舍入。
高桥想要选择 l 以最佳方式最小化操作后的最高温度, \displaystyle\max_{1 \leq i \leq N} F'_i.
找出该最大值的最小可能值。
约束
- 1 \leq K \leq N \leq 10^6
- -10^9 \leq F_i \leq 10^9
- N, K 是整数
- F_i 是整数
输入
N K F_1 F_2 \ldots F_N
- 第一行包含整数 N 代表观测站数量和整数 K 表示平滑过程中选择的连续站数,以空格分隔。
- 第二行包含整数 F_1, F_2, \ldots, F_N 代表每个观测站的温度,以空格分隔。
输出
在一行中输出平滑处理后的最高温度的最小可能值。请注意,虽然运算中的平均值被计算为精确的实数,但如果与真实值的绝对误差或相对误差最多为,则输出将被视为正确 10^{-6}.
示例输入 1
5 2 3 10 4 2 8
示例输出 1
8.0000000000
示例输入 2
6 3 -5 0 -2 7 1 -3
示例输出 2
1.6666666667
示例输入 3
12 4 15 -3 22 8 7 30 -10 5 18 12 -4 25
示例输出 3
25.0000000000
示例输入 4
30 7 100 -50 23 75 -10 200 0 45 90 -80 60 110 -30 15 5 130 -100 70 85 -20 40 95 -60 150 10 -5 55 120 -90 35
示例输出 4
150.0000000000
示例输入 5
1 1 -1000000000
示例输出 5
-1000000000.0000000000