Moe's CF Life

哈喽，主人！今天又是元气满满的一天，喵~ 🐾

Polycarp 小哥好像因为失眠睡不好觉，真是让人担心呢。不过别怕，他有我们来帮忙计算平均睡眠时间，一定能让他安心的！让本喵带你一步一步解决这个问题吧！

题目大意

简单来说，这道题是这样的喵：

Polycarp 记录了他连续 n 天的睡眠时长，每天睡了 a_i 小时。他想知道他“每周”的平均睡眠时间。这里的“周”比较特别，不是固定的7天，而是连续的 k 天。

我们需要找出所有可能的、连续 k 天的“周”。比如从第1天到第k天是第一周，第2天到第k+1天是第二周，以此类推，直到最后一周（从第 n-k+1 天到第 n 天）。

我们的任务是：

计算出每一“周”的总睡眠时长。
把所有“周”的总睡眠时长再加起来，得到一个总和。
最后，用这个总和除以“周”的总数量（也就是 n-k+1），得到最终的平均值。

听起来是不是很简单呀？就像把一堆小鱼干先分成几份，再算每份的平均重量一样，喵~

题解方法

如果直接按照题目描述来计算，我们可能会这样做：

写一个循环，从第一天开始，遍历所有可能的“周”的起始点（总共有 n-k+1 个）。
在每个起始点，再用一个循环，把后面 k 天的睡眠时间加起来。

这样做虽然没错，但是当 n 和 k 很大的时候，两个循环嵌套会让程序跑得像刚睡醒的猫猫一样慢，可能会超时哦！

所以，本喵想到了一个更聪明的办法——滑动窗口（Sliding Window）！

想象一下，我们有一个大小为 k 的窗口，正盖在表示睡眠时长的数组上。

首先，我们计算第一个窗口（第1天到第k天）的总和。
然后，当窗口向右滑动一格时，我们不需要重新计算新窗口里所有 k 个数的和。你看，新窗口只是比旧窗口增加了一个新元素（在右边），同时丢掉了一个旧元素（在左边）。
所以，我们只要用上一个窗口的和，减去离开窗口的那个数，再加上新进入窗口的数，就能立刻得到新窗口的和啦！

这个过程就像猫猫用爪子把毛线球往前推一样，每次只动一下下，非常高效！我们只需要从头到尾把数组“滑”一遍，就能算出所有窗口的和了，时间复杂度从 O(n*k) 降到了 O(n)，快多啦，喵！

题解代码

这是本喵为主人准备好的 C++ 代码，里面加了一些注释，方便理解哦~

cpp

#include <iostream>
#include <vector>
#include <iomanip> // 别忘了这个库，用来控制输出精度的喵

int main() {
    // 使用这两行可以让输入输出更快，对付大数据时很有用！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    // 读取天数 n 和每周天数 k
    int n, k;
    std::cin >> n >> k;

    // 读取每天的睡眠时长
    std::vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
    }

    // 注意！因为 n 和 k 的值都很大，它们的乘积可能会超出普通整数的范围。
    // 就像一个碗装不下太多小鱼干一样，所以我们要用 long long 这种大碗来装总和，防止溢出喵！
    long long current_window_sum = 0;

    // 第一步：计算第一个窗口（前 k 天）的总和
    for (int i = 0; i < k; ++i) {
        current_window_sum += a[i];
    }

    // 这个变量用来存储所有窗口总和的“总和”，也需要用 long long 哦
    long long total_sum_of_sums = current_window_sum;

    // 第二步：开始滑动窗口！
    // 循环从第 k 个元素开始（也就是新进入窗口的第一个元素）
    for (int i = k; i < n; ++i) {
        // 滑动窗口的核心操作：
        // 加上新来的 a[i]，减去溜走的 a[i-k]
        current_window_sum += a[i] - a[i - k];
        
        // 把当前窗口的和累加到总和里
        total_sum_of_sums += current_window_sum;
    }

    // "周"的总数是 n - k + 1
    long long num_windows = n - k + 1;

    // 计算最终的平均值。为了得到小数，需要把其中一个数转成 double 类型
    double average = static_cast<double>(total_sum_of_sums) / num_windows;

    // 按照题目要求，输出结果并保留足够的小数位数
    std::cout << std::fixed << std::setprecision(15) << average << std::endl;

    return 0;
}

知识点介绍

这道题里，我们用到的最核心的技巧就是 滑动窗口算法 (Sliding Window Algorithm) 啦！

什么是滑动窗口？

滑动窗口是一个非常经典且有用的算法思想。它通常用于解决数组或字符串上的子区间（或子串）问题。你可以把它想象成一个固定大小的“框框”，在数据序列上平移。

它有什么优点？

最大的优点就是高效！对于需要反复计算一个固定大小区间内某些属性（比如和、最大值、最小值）的问题，滑动窗口可以将时间复杂度从 O(N*K) 优化到 O(N)。这是因为它巧妙地利用了相邻窗口之间的关系，避免了大量的重复计算。

什么时候用它？

当你遇到类似下面的问题时，就可以考虑一下滑动窗口了喵：

在一个数组中，找出所有长度为 k 的子数组的和。 (就是我们这道题！)
在一个数组中，找出所有长度为 k 的子数组中的最大值。
在一个字符串中，找出包含所有特定字符的最短子串。

除了滑动窗口，解决这类“区间和”问题还有一个好朋友，叫做 前缀和 (Prefix Sum)。

什么是前缀和？

前缀和数组 prefix_sum 的第 i 个元素存储的是原数组从第 0 个到第 i 个元素的总和。预处理出这个数组后，我们就可以在 O(1) 的时间内得到任意区间 [i, j] 的和，公式是 prefix_sum[j] - prefix_sum[i-1]。用前缀和也能高效地解决这道题哦！

好啦，这次的题解就到这里啦！希望对主人有帮助喵~ 如果还有什么问题，随时可以再来找我玩！(=^･ω･^=)

题目大意 ​

题解方法 ​

题解代码 ​

知识点介绍 ​

题目大意

题解方法

题解代码

知识点介绍