喵~ 各位程序员哥哥姐姐们好呀！本喵是乃们的贴心解题小助教，今天也要元气满满地和大家一起攻克难题哦！这次我们要看的题目是 Codeforces 上的 1133C - Balanced Team，一个关于组建最强战队的问题，听起来就很有趣，对吧？那么，就让本喵带大家一起来看看吧，喵~

C. Balanced Team | 和猫娘一起组建最强战队喵~

---

题目大意

作为一名大学的编程竞赛教练，你手下有 n 个学生，每个学生都有一个编程能力值 a_i。

你的任务是组建一支参加新比赛的队伍。我们都知道，队伍里的人越多，获胜的可能性就越大！所以你想让队伍的人数尽可能多。但是呢，队伍也需要是 “平衡的”。一个平衡的队伍意味着，队伍中 任意两名 学生的编程能力值之差 不能超过 5。

现在，请你计算一下，一支平衡的队伍最多可以有多少名学生呢？

简单来说，就是从一群学生里选出尽可能多的人，让他们组成一个小组，要求小组里能力最强和能力最弱的同学，他们的能力值差距不能大于 5。就像我们猫猫们一起玩耍，不能有谁被落下太多嘛，对不对喵？

---

题解方法

这个问题看起来需要我们检查所有可能的学生组合，但那样也太慢啦，本喵的爪子可受不了！肯定有更聪明的办法，喵！

核心思路：排序 + 滑动窗口（双指针）

1. 排序 首先呀，我们先把所有同学的能力值 a 从小到大排个序。这样做有一个天大的好处：排好序之后，一个“平衡的”队伍，它的成员在排序后的数组里，肯定是 连续的一段！ 为什么呢？你想呀，如果我们选了能力值为 x 和 y ( x < y ) 的两个同学，并且他们满足 y - x <= 5。那么任何能力值在 x 和 y 之间的同学，是不是也都可以加入这个队伍，并且不会破坏“平衡”的条件？当然可以啦！所以，我们只需要在排好序的数组里，寻找最长的一段连续子数组，满足其最大值（最右边的元素）与最小值（最左边的元素）之差不大于 5 就可以啦。

2. 滑动窗口（双指针） 找到了这个突破口，问题就变成了“在有序数组中寻找满足 a[j] - a[i] <= 5 的最长子数组 [i, j]”。 这时候，我们就可以派出非常厉害的 双指针 技巧啦！也叫 滑动窗口，或者 尺取法，名字好多，但思想很可爱，喵~

   • 我们用两个指针，一个叫 l（left，左爪爪），一个叫 r（right，右爪爪）。它们一起圈定了一个“窗口”，也就是一个潜在的队伍 [l, r]。
   • 一开始，l 和 r 都在数组的最左边（位置0）。
   • 然后，我们让右爪爪 r 向右移动，每次尝试把一个新同学拉进队伍里。
   • 每当 r 移动一次，我们就检查一下现在的窗口（队伍）是否还“平衡”，也就是 a[r] - a[l] <= 5。
     • 如果 是平衡的，太棒啦！这个窗口 [l, r] 是一个合法的队伍。它的长度是 r - l + 1，我们用这个长度去更新我们找到过的最大队伍人数。
     • 如果 不平衡了 (a[r] - a[l] > 5)，哎呀，说明最左边的同学 a[l] 和新来的同学 a[r] 能力差距太大了。为了让队伍重新平衡，我们只好把左爪爪 l 向右移动，也就是让 a[l] 这位同学暂时离开窗口。我们一直移动 l，直到窗口再次满足 a[r] - a[l] <= 5 为止。
   • 右爪爪 r 就这样一路走到数组的最末端，我们也就找到了所有可能的窗口，并记录下了其中最长的那一个。

这个过程就像一个伸缩的尺子，右边不断往外伸，如果发现尺子里的两端差距太大了，就从左边缩回来一点，始终保持尺子内的范围是合格的，然后在这个过程中记录下尺子的最大长度。是不是很形象呀，喵~

---

题解

下面就是本喵为大家准备的 C++ 代码啦，加上了可爱的注释哦！

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

int main() {
    // 为了让输入输出快一点，像猫咪跑一样快！喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n;
    std::cin >> n; // 读取学生的数量
    std::vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i]; // 读取每个学生的能力值
    }

    // 第一步：先把所有同学按能力值排个序，从小到大站好队~
    std::sort(a.begin(), a.end());

    // 如果只有一个学生，那队伍最多也就一个人啦
    if (n <= 1) {
        std::cout << n << std::endl;
        return 0;
    }

    // 第二步：使用滑动窗口（双指针）来寻找最长的平衡队伍
    int l = 0; // 左指针（左爪爪），指向窗口的开始
    int max_len = 0; // 用来记录找到的最长队伍的人数

    // 右指针 r（右爪爪）从头开始遍历整个数组
    for (int r = 0; r < n; ++r) {
        // 当窗口不平衡时（最大值 a[r] - 最小值 a[l] > 5）
        // 我们就需要把左指针 l 向右移动，缩小窗口
        while (a[r] - a[l] > 5) {
            l++;
        }
        
        // 经过 while 循环后，当前的窗口 [l, r] 一定是平衡的
        // 我们计算当前窗口的长度，并更新最大长度
        // 窗口长度是 r - l + 1
        max_len = std::max(max_len, r - l + 1);
    }

    // 输出我们找到的最大队伍人数
    std::cout << max_len << std::endl;

    return 0;
}

---

知识点介绍

这道题主要用到了两个非常基础但又超级重要的算法知识点，喵~

1. 排序 (Sorting)

   • 是什么：排序就是将一组数据按照指定的顺序（比如从小到大或从大到小）重新排列的过程。
   • 为什么重要：排序是许多算法的前置步骤。在本题中，排序将一个看似复杂的问题（在任意组合中寻找满足条件的子集）简化为了一个更简单的问题（在有序序列中寻找满足条件的连续子段）。这大大降低了问题的复杂度。

2. 双指针 / 滑动窗口 (Two Pointers / Sliding Window)

   • 是什么：这是一种非常高效的算法技巧，通常用于处理数组或链表问题。它通过维护两个（或多个）指针，并根据特定规则移动它们来遍历数据，从而在一次遍历中解决问题。
   • 优点：双指针/滑动窗口的核心优势在于其 线性时间复杂度 O(N)。相比于朴素的 O(N^2) 暴力解法（即检查所有可能的子数组），它极大地提高了算法的效率。
   • 适用场景：它特别适合解决那些需要在序列中寻找满足特定属性的 连续子序列 的问题，就像我们这道题一样。
   • 在本题中的体现：我们用 l 和 r 两个指针维护了一个“窗口”。r 负责扩大窗口，l 负责在不满足条件时收缩窗口。两个指针都只从左向右移动，绝不后退，保证了整个过程是线性的。

掌握了双指针，就能像猫咪一样，用两只灵活的爪爪在数组上探索，高效地解决问题啦，喵~

好啦，今天的题解就到这里！希望本喵的讲解对大家有帮助哦。下次再见喵！(ฅ'ω'ฅ)