喵~ 主人，你好呀！今天本喵要给你讲解一道非常有趣的算法题：Codeforces 580B - Kefa and Company。这道题就像是为 Kefa 找一群能和睦相处的猫猫朋友开派对一样，既要大家开心（友谊值高），又不能有猫猫因为自己的小鱼干比别人少太多而难过（贫富差距小）。

就让本喵带你一步步拆解这道题，找到最棒的派对组合吧！

题目大意

Kefa 发了第一笔大工资，超开心的，想请朋友们去餐厅搓一顿！他有 n 个朋友，每个朋友都有两个属性：拥有的钱 m 和与 Kefa 的友谊值 s。

Kefa 举办派对有一个特殊的规矩，喵~ 他不希望有任何朋友在派对上感到“贫穷”。一个朋友如果看到派对里有另一个人的钱比自己至少多 d，他就会感到贫穷。

所以，Kefa 邀请的派对成员必须满足这个条件：派对中任意两个朋友的钱数之差都必须小于 d。

Kefa 的目标是，在满足这个条件的前提下，让被邀请的所有朋友的友谊值总和最大。我们要做的就是帮 Kefa 算出这个最大的友谊值总和是多少，的说。

---

解题方法

一看到要从 n 个朋友中选出一部分，让某个总和最大，有些主人可能会想到暴力搜索，把所有可能的组合都试一遍。但是 n 高达 10^5，2^n 的复杂度会让电脑直接罢工的，绝对不行喵！

所以，我们需要更聪明的办法。

第一步：排序！

这个问题的核心是钱的差值。如果我们把朋友们的信息弄得乱七八糟，每次检查一个组合是否满足 钱数差 < d 的条件就会很麻烦。

但是，如果我们先把所有朋友按照他们拥有的钱数 m 从小到大排个序呢？

排序之后，对于任意一个连续区间的朋友 [i, j]（假设 i <= j），最有钱的就是第 j 个朋友，最“穷”的就是第 i 个朋友。那么，检查这一整个区间的成员是否满足条件，就只需要比较他们两个就行啦！也就是判断 friends[j].m - friends[i].m < d 是否成立。如果他们俩都满足，那么中间的任何朋友也肯定满足，因为他们的钱数都在 friends[i].m 和 friends[j].m 之间嘛。

这样一来，问题就从“寻找任意子集”简化为“寻找一个排序后的连续子数组”，使得这个子数组满足条件，并且友谊值之和最大。这可简单多啦，喵~

第二步：滑动窗口！

现在问题变成了寻找一个满足条件的连续子数组。这种问题，用滑动窗口（也叫双指针）技巧是再合适不过了！

我们可以想象有两只猫爪，left 和 right，它们在排好序的朋友列表上划定了一个“窗口”，这个窗口就代表我们当前考虑的派对团体。

1. 初始化：left 和 right 指针都从第 0 个朋友开始。我们还需要一个变量 current_friendship 来记录当前窗口内朋友们的友谊值总和，一个变量 max_friendship 来记录我们找到过的最大友-谊值总和。

2. 窗口扩张：我们让 right 指针（右爪）向右移动，每次“抓”进来一个新的朋友。同时，把这个新朋友的友谊值加到 current_friendship 中。

3. 窗口收缩：每当加入一个新朋友后，我们都要检查一下当前窗口是否还满足“贫富差距”的条件。也就是检查 friends[right].m - friends[left].m >= d。

   • 如果这个条件成立了，说明当前窗口最右边的朋友太有钱了，导致最左边的朋友感到了“贫穷”。怎么办呢？我们就要把 left 指针（左爪）向右移动，把最“穷”的朋友从派对里请出去，直到窗口重新满足条件为止。别忘了，请出去一个朋友，就要从 current_friendship 中减掉他的友谊值。

4. 更新答案：在每一次扩张 right 指针，并确保窗口有效之后，当前的 current_friendship 就是一个合法的派对方案的友谊值总和。我们用它和 max_friendship 比较，如果当前更大，就更新 max_friendship。

right 指针从头走到尾之后，max_friendship 里存的就是我们能找到的最终答案啦！整个过程，left 和 right 指针都只向右移动，每个朋友最多被 right 指针访问一次，被 left 指针访问一次，所以滑动窗口的复杂度是 O(n)，加上排序的 O(n log n)，总复杂度就是 O(n log n)，非常高效，喵！

---

题解代码 (C++)

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

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

// 用一个结构体来存放朋友的信息，这样代码更清晰喵~
struct Friend {
    int m; // 钱钱
    int s; // 友谊值
};

int main() {
    // 这两行是C++的加速咒语，对付大数据量输入输出很有用！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n;
    long long d; // d 可能是个大数字，用 long long 更安全
    std::cin >> n >> d;

    // 用 vector 存放所有的朋友
    std::vector<Friend> friends(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> friends[i].m >> friends[i].s;
    }

    // 关键一步：按照钱数 m 从小到大排序
    // lambda 表达式 `[](...)` 用来告诉 sort 如何比较两个 Friend 对象
    std::sort(friends.begin(), friends.end(), [](const Friend& a, const Friend& b) {
        return a.m < b.m;
    });

    long long max_friendship = 0;
    long long current_friendship = 0;
    int left = 0; // 滑动窗口的左指针

    // right 指针遍历所有朋友，作为窗口的右边界
    for (int right = 0; right < n; ++right) {
        // 1. 窗口扩张：把 right 指向的朋友加入窗口
        current_friendship += friends[right].s;

        // 2. 窗口收缩：检查窗口是否有效
        // 如果最有钱的(right)和最没钱的(left)差距过大...
        while (friends[right].m - friends[left].m >= d) {
            // ...就把最没钱的(left)请出窗口
            current_friendship -= friends[left].s;
            left++; // 左指针向右移动
        }

        // 3. 更新答案：当前窗口 [left, right] 是一个有效的派对组合
        // 我们看看它的友谊值总和是不是目前最大的
        max_friendship = std::max(max_friendship, current_friendship);
    }

    // 输出最终找到的最大友谊值
    std::cout << max_friendship << std::endl;

    return 0;
}

---

知识点介绍

这道题主要用到了两个非常基础但强大的知识点，主人可要好好掌握哦！

1. 排序 (Sorting)

   • 是什么：排序就是把一组数据按照指定的规则（比如从小到大）重新排列。
   • 为什么重要：在本题中，排序是解题的钥匙！它将一个复杂的问题（在任意子集中寻找满足条件的组合）简化为了一个线性问题（在连续子数组中寻找）。很多看起来棘手的问题，在排序后都会变得清晰明了，所以遇到问题时不妨先想想排序能不能帮上忙，喵~
   • 复杂度：像 C++ std::sort 这样的高效排序算法，时间复杂度通常是 O(n log n)。

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

   • 是什么：这是一种算法技巧，通过维护两个指针（通常叫 left 和 right）来定义一个“窗口”或“区间”。这两个指针通常都朝同一个方向移动。
   • 用来做什么：它非常适合解决在连续数组或字符串上寻找满足某些条件的最长/最短/最优子区间的问题。
   • 优点：滑动窗口通过巧妙地移动指针，避免了重复计算，能将暴力解法中 O(n²) 或 O(n³) 的复杂度降低到 O(n)。因为每个元素最多被 left 和 right 指针各访问一次，所以效率极高。

希望本喵的讲解对主人有帮助！如果还有不明白的地方，随时可以再来问我哦，喵~