分数: 300 分
问题陈述
高桥正在做一份兼职工作,分析一家连锁店的销售数据。
该连锁店有销售记录 N 天,以及当天的销售额 i (1 \leq i \leq N) 是 T_i 日元。
高桥想要计算每个连续的平均销售额 K天期间并找到最大值,以便了解销售最好的期间的表现。
具体来说,对于每个整数 l (1 \leq l \leq N - K + 1),连续两年的平均销售额 K 天数 l 到今天 l + K - 1 定义为
M_l = \frac{T_l + T_{l+1} + \cdots + T_{l+K-1}}{K}
让 M 是最大值 M_l 总的来说 l (1 \leq l \leq N - K + 1).
查找 \lfloor M \times 1000 \rfloor,其中 \lfloor x \rfloor 表示不超过的最大整数 x (楼层功能)。这对应于截断 M 小数点后第四位以下并乘以 1000.
提示: 让 S 是任何连续销售的最大总和 K 天。既然所有 T_i 是整数, S 也是一个整数,并且 \lfloor M \times 1000 \rfloor = \left\lfloor \frac{1000 \times S}{K} \right\rfloor 成立。因此,可以仅使用整数算术来计算答案。
约束
- 1 \leq K \leq N \leq 2 \times 10^5
- 1 \leq T_i \leq 10^6
- 所有输入均为整数
输入
N K T_1 T_2 \cdots T_N
- 第一行包含整数 N 代表销售记录的天数和整数 K 代表句点的长度,以空格分隔。
- 第二行包含整数 T_1, T_2, \ldots, T_N 代表每天的销售额,以空格分隔。
输出
让 M 是任何连续的最大平均销售额 K天期间。输出的值 \lfloor M \times 1000 \rfloor 在一行上。
示例输入 1
5 3 10 20 30 25 15
示例输出 1
25000
示例输入 2
7 2 100 150 80 200 190 50 120
示例输出 2
195000
示例输入 3
10 4 1234 5678 9012 3456 7890 2345 6789 1357 2468 8024
示例输出 3
6509000