最大平均值问题

题目描述

农夫约翰的农场由 $N$ 块田地组成，每块地里都有一定数量的牛，其数量不会少于 $1$ 头，也不会超过 $2000$ 头。

约翰希望用围栏将一部分连续的田地围起来，并使得围起来的区域内每块地包含的牛的数量的平均值达到最大。

围起区域内至少需要包含 $F$ 块地，其中 $F$ 会在输入中给出。

在给定条件下，计算围起区域内每块地包含的牛的数量的平均值可能的最大值是多少。

输入格式

第一行输入整数 $N$ 和 $F$，数据间用空格隔开。

接下来 $N$ 行，每行输入一个整数，第 $i+1$ 行输入的整数代表第 $i$ 片区域内包含的牛的数目。

输出格式

输出一个整数，表示平均值的最大值乘以 $1000$ 再 向下取整 之后得到的结果。

输入输出样例 #1

输入 #1

10 6
6
4
2
10
3
8
5
9
4
1

输出 #1

6500

输入输出样例 #2

输入 #2

5 3
1
2
3
4
5

输出 #2

4000

限制条件

• $1 \le N \le 100000$
• $1 \le F \le N$
• 每块地的牛数量 $1 \le a_i \le 2000$

样例解释 #1

有 $10$ 块田地，牛的数量分别为：$[6, 4, 2, 10, 3, 8, 5, 9, 4, 1]$

需要选择至少 $6$ 块连续的田地，使得平均值最大。

最优选择是选择第 $4$ 到第 $9$ 块田地：$[10, 3, 8, 5, 9, 4]$

总牛数 = $10 + 3 + 8 + 5 + 9 + 4 = 39$

平均值 = $39 / 6 = 6.5$

乘以 $1000$ 并向下取整：$6.5 \times 1000 = 6500$

因此输出 $6500$。

注意

由于需要输出平均值乘以 $1000$ 并向下取整，因此实际计算的是 $1000$ 倍平均值的整数部分。