b3408 [usaco2009 oct]heat wave 热浪

题目描述：

给定一个长度为n的序列a，每个元素表示第i天的温度。现在你要在这个序列中选择一个长度为k的连续子序列，使得这个子序列的平均温度最高。求出这个最高的平均温度。

输入格式：

第一行包含两个整数n和k，表示序列长度和子序列长度。

第二行包含n个整数，表示序列a。

输出格式：

输出一个数字，表示最高的平均温度，保留两位小数。

输入样例：

5 3
1 2 3 4 5

输出样例：

4.00

算法1

(暴力枚举) $O(n^2)$

暴力枚举所有长度为k的子序列，计算平均温度，取最大值。

时间复杂度

暴力枚举所有长度为k的子序列，时间复杂度为O(n^2)。

C++ 代码

算法2

(滑动窗口) $O(n)$

使用滑动窗口，每次移动一个单位，计算当前窗口内的平均温度，取最大值。

时间复杂度

使用滑动窗口，时间复杂度为O(n)。

C++ 代码