← 返回题目列表

AtCoder · awc0108_c

C. 平滑温度

中文机器翻译题面 查看原题

分数: 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