喵~ 主人，你好呀！今天我们来看一道非常有趣的题目，就像是在一堆毛线球里找到最长的一串，然后开心地玩耍一样，嘿嘿~ 这道题是关于 Valera 小哥读书的，让我们一起来帮帮他吧！

B. Books (CF 279B)

题目大意喵~

Valera 有 n 本书排成一排，还有总共 t 分钟的空闲时间。对于第 i 本书，他需要 a[i] 分钟来读完。

他的读书方式有点特别哦：他会选择任意一本书 i 作为起点，然后按顺序一本一本地读下去（i, i+1, i+2, ...），直到发生以下两种情况之一：

1. 他的空闲时间不够读下一本书了。
2. 他已经读完了最后一本（第 n 本）书。

Valera 是个有始有终的好孩子，如果时间不够读完整本书，他是不会开始读的。

我们的任务就是，找出 Valera 最多能读多少本书。

举个栗子： 假设有 4 本书，阅读时间分别是 [3, 1, 2, 1]，总时间是 5 分钟。

• 如果从第 1 本开始读：读完第 1 本（3分钟），还剩 2 分钟。再读第 2 本（1分钟），还剩 1 分钟。此时没法读第 3 本（需要2分钟），所以总共读了 [3, 1] 这 2 本书。
• 如果从第 2 本开始读：读完第 2 本（1分钟），还剩 4 分钟。读第 3 本（2分钟），还剩 2 分钟。读第 4 本（1分钟），还剩 1 分钟。总共读了 [1, 2, 1] 这 3 本书。 所以，最多可以读 3 本书。

---

解题方法思路喵！

这个问题，就像是我们要在一个长长的书架上，用一个能伸缩的框框圈出一部分连续的书，要求这些书的总阅读时间不能超过 t，并且我们想让这个框框里的书尽可能多！

这种“可伸缩的框框”问题，在算法里有一个非常可爱的名字，叫做 “滑动窗口” 算法，喵~

我们可以用两个指针，left 和 right，来代表我们窗口的左右边界。right 指针负责向右探索，把新的书纳入窗口；left 指针则在窗口“太满”的时候，向右移动，把旧的书移出窗口。

具体步骤是这样哒：

1. 初始化：

   • left 指针和 right 指针都指向第一本书（下标为 0）。
   • current_sum 用来记录当前窗口内所有书的总阅读时间，初始为 0。
   • max_books 用来记录我们找到的最多能读的书本数量，初始为 0。

2. 窗口扩张：

   • 我们用一个循环，让 right 指针从头到尾遍历所有的书。
   • 每当 right 指针移动一次，我们就把新指向的书的阅读时间加到 current_sum 里。这就像是把一本新书放进了我们的阅读计划中。

3. 窗口收缩：

   • 在加入一本新书后，我们得检查一下 current_sum 是不是超过了总时间 t。
   • 如果 current_sum > t，说明我们的阅读计划太贪心啦，时间不够了！这时候，我们就需要从窗口的左边拿掉一本书，也就是让 left 指针向右移动，并从 current_sum 中减去 a[left] 的时间。
   • 这个收缩的过程可能会进行好几次，直到 current_sum <= t 为止，窗口才重新变得“合法”。

4. 更新答案：

   • 每当 right 指针移动一步，并且窗口调整（可能收缩）完毕后，此时的窗口 [left, right] 内的书就是一个可行的阅读方案。
   • 窗口内的书本数量就是 right - left + 1。
   • 我们用这个数量和当前的 max_books 比较，取其中较大的一个来更新 max_books。max_books = max(max_books, right - left + 1)。

5. 结束：

   • 当 right 指针遍历完所有书之后，max_books 里存的就是最终的答案啦！

这个方法非常高效，因为每个指针都只从左到右移动了一遍，所以时间复杂度是 O(n) 哦，非常快，就像猫咪追光点一样迅速！

---

题解代码 (C++)

这是解题的 C++ 代码，我已经加上了可爱的注释，喵~

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    // 为了让程序跑得快一点，像小猫快跑一样！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    // n 是书本数量, t 是总时间
    int n;
    long long t;
    std::cin >> n >> t;

    // a 是一个向量，用来存放每本书的阅读时间
    std::vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
    }

    // 滑动窗口的变量们~
    int left = 0;              // 窗口的左爪子
    long long current_sum = 0; // 窗口内书本的总阅读时间
    int max_books = 0;         // 我们找到的最多能读的书本数量

    // right 指针是窗口的右爪子，它会一直向右探索
    for (int right = 0; right < n; ++right) {
        // 把新书放进窗口，增加总时间
        current_sum += a[right];

        // 如果时间超了，就要把左边的书拿出去，直到时间够用为止
        while (current_sum > t) {
            current_sum -= a[left];
            left++; // 左爪子向右挪一格
        }

        // 现在窗口 [left, right] 是一个合法的方案
        // 窗口里的书本数量是 right - left + 1
        // 看看这个方案是不是比之前找到的更好呀？
        max_books = std::max(max_books, right - left + 1);
    }

    // 把最好的结果告诉 Valera！
    std::cout << max_books << std::endl;

    return 0;
}

---

知识点小课堂：滑动窗口 (Sliding Window)

滑动窗口 是一种非常常见且强大的算法技巧，主要用于解决数组或字符串上的子区间（子数组/子串）问题。它就像一个在数据序列上滑动的窗户，窗户的大小可以是固定的，也可以是可变的。

核心思想： 通过维护一个窗口（通常由 left 和 right 两个指针界定），来减少不必要的重复计算。当窗口不满足条件时，不是从头再来，而是在现有窗口的基础上进行调整（通常是移动左边界），从而达到线性的时间复杂度。

适用场景： 当你看到题目要求在 连续的子数组/子串 上寻找满足某些条件的 最长/最短 或者 计数 问题时，就可以考虑一下滑动窗口啦！

与暴力解法的对比：

• 暴力解法：可能会枚举所有可能的连续子数组。比如，对于本题，就是枚举每一个起始点 i，然后再向后累加，直到时间不够。这样做的复杂度是 O(n²)，当 n 很大时（比如 10^5），就会超时。
• 滑动窗口：left 和 right 指针都只从头到尾遍历一次数组，所以总的时间复杂度是 O(n)。对于 n = 10^5 的数据规模来说，完全没有问题，非常高效！

希望这次的讲解对你有帮助哦！如果还有问题，随时可以再来找我，喵~ ❤️