Moe's CF Life

喵~ 主人，今天我们来看一道关于朋友们去餐厅的有趣问题呀！(ฅ'ω'ฅ)

这道题是 Codeforces 上的 1729D. Friends and the Restaurant。让本猫娘来给你细细讲解一下吧！

题目大意

有一群 n 个朋友，他们想一起去餐厅吃饭，但是呢，他们决定分几天去。

每一天，都会有一个至少两人的小组去餐厅。每个朋友最多只能去一次，所以不同天去的小组里不能有相同的朋友。

对于第 i 个朋友，他计划花 x_i 的钱，但他身上只有 y_i 的钱。

一个小组能够成功去吃饭的条件是：这个小组里所有朋友带的总钱数，必须大于或等于他们计划要花的总钱数。也就是说，对于一个小组，他们所有人的 y_i 之和要 >= 他们所有人的 x_i 之和。

那么问题来啦：这群朋友最多可以组成多少个这样的小组，也就是最多可以去餐厅多少天呢？

举个例子：有6个朋友，计划花费 x = [8, 3, 9, 2, 4, 5]，拥有金钱 y = [5, 3, 1, 4, 5, 10]。我们可以让第1个和第6个朋友组队：

花费：x_1 + x_6 = 8 + 5 = 13
预算：y_1 + y_6 = 5 + 10 = 15
因为 15 >= 13，所以他们可以组成一个小组，这是第1天。

剩下的朋友里，第2、4、5个朋友可以组队：

花费：x_2 + x_4 + x_5 = 3 + 2 + 4 = 9
预算：y_2 + y_4 + y_5 = 3 + 4 + 5 = 12
因为 12 >= 9，他们也可以组成一个小组，这是第2天。

这样最多可以组成2个小组，所以答案就是2天。剩下的第3个朋友就只能自己待在家里了，喵呜~

解题思路

这道题的目标是最大化组队的数量。一看到“最大化”这个词，本猫娘的直觉就告诉我要往贪心的方向去想啦！

首先，我们来简化一下组队的条件。一个小组能够成立，需要满足 sum(y_i) >= sum(x_i)。这个不等式可以变形一下，喵~ sum(y_i) - sum(x_i) >= 0sum(y_i - x_i) >= 0

这样一来，问题就清晰多啦！我们可以为每个朋友计算一个“差值” d_i = y_i - x_i。

如果 d_i >= 0，说明这个朋友很有钱，花完计划的钱还有结余，我们叫他“富裕”的朋友。
如果 d_i < 0，说明这个朋友钱不够，需要别人帮忙才能凑够饭钱，我们叫他“贫穷”的朋友。

现在，问题就变成了：将这些朋友（和他们的差值 d_i）分成若干个小组（每组至少两人），使得每个小组的 d_i 之和都大于等于0。我们要让这样的小组数量最多。

怎么贪心才能让小组数量最多呢？为了尽可能多地凑出小组，我们应该优先考虑最“困难”的情况。最困难的是哪个朋友？当然是 d_i 最小的那个，也就是最“贫穷”的朋友啦。他需要最多的帮助。

那么谁能最好地帮助他呢？当然是 d_i 最大的那个，最“富裕”的朋友！如果连最富裕的朋友都无法和最贫穷的朋友凑成一队（即他们的 d_i 之和小于0），那么这个最贫穷的朋友就没救了，因为其他任何人都比不上最富裕的朋友有钱，也就不可能和他组队了。这种情况下，这个最贫穷的朋友就只能被放弃了，喵~

如果最富裕的朋友可以和最贫穷的朋友组队成功，那真是太好了！我们成功拯救了一个最难配对的人，组成了一个小组。这无疑是当前最优的选择，因为我们用一个“富裕”名额解决了一个最棘手的“贫穷”名额。

基于这个想法，我们可以得到一个清晰的贪心策略：

计算出所有朋友的差值 d_i = y_i - x_i。
将这些差值 d_i 从小到大排序。这样，数组的开头就是最“贫穷”的朋友，数组的末尾就是最“富裕”的朋友。
使用双指针，一个指针 l 指向数组开头（最穷的），一个指针 r 指向数组末尾（最富的）。
尝试将 l 和 r 指向的朋友配对：
- 如果 d[l] + d[r] >= 0，太棒了！他们可以组成一队。我们就让他们组队，小组数加一，然后两个指针都向中间移动 (l++, r--)，去考虑剩下的人。
- 如果 d[l] + d[r] < 0，说明最富裕的朋友也带不动最贫穷的朋友。那么这个贫穷的朋友就注定无法和任何人组队了。我们只好放弃他，让 l 指针向右移动 (l++)，去看看下一个稍微不那么穷的朋友有没有机会。而富裕的朋友 r 先不动，他或许还能帮助别人。
当 l 指针和 r 指针相遇或交错时，就停止配对。

这个策略每次都尝试用最优的资源（最有钱的人）去解决最困难的问题（最穷的人），从而确保了能凑出的队伍数量是最大的。而且我们每次都组成两人小队，因为组成更多人的小队并不会比两人小队更优。比如三个人 A, B, C 组队，如果 A, B 两个人就能组队，那让他们俩组队，C 去和别人组队，可能会得到更多的小组。

题解代码

下面就是用 C++ 实现的解法啦，人家加了详细的注释哦！

cpp

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

// 处理单个测试用例的函数喵
void solve() {
    int n;
    std::cin >> n;

    // 读取朋友们计划的花费 x_i
    std::vector<long long> x(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> x[i];
    }

    // 读取朋友们拥有的金钱 y_i
    std::vector<long long> y(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> y[i];
    }

    // 计算每个朋友的差值 d_i = y_i - x_i
    // d_i >= 0 表示这个朋友有结余（富裕）
    // d_i < 0 表示这个朋友钱不够（贫穷）
    std::vector<long long> d(n);
    for (int i = 0; i < n; ++i) {
        d[i] = y[i] - x[i];
    }

    // 将差值数组 d 从小到大排序
    // 这样数组最左边是赤字最大的，最右边是盈余最多的
    std::sort(d.begin(), d.end());

    // 使用双指针来寻找可以配对的朋友
    int l = 0;      // 左指针，指向当前最“穷”的朋友
    int r = n - 1;  // 右指针，指向当前最“富”的朋友
    int groups = 0; // 记录成功组成的小组数量

    while (l < r) {
        // 尝试将最穷的和最富的配对
        if (d[l] + d[r] >= 0) {
            // 如果他们的差值之和大于等于0，说明他们可以组成一个有效的小组
            groups++; // 小组数+1
            l++;      // 这两位朋友都用掉了，指针向中间移动
            r--;
        } else {
            // 如果差值之和小于0，说明即使是最富的朋友也无法帮助最穷的这位
            // 那么这位最穷的朋友就无法和任何人组队了（因为其他人更穷）
            // 所以我们只能放弃他，移动左指针
            l++;
        }
    }

    std::cout << groups << "\n";
}

int main() {
    // 加速一下输入输出，让程序跑得更快，喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

知识点介绍

这道题主要用到了两个很重要的算法思想，主人可要记好啦！

贪心算法 (Greedy Algorithm) 贪心算法是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的算法。在这道题里，我们的贪心策略是：每次都尝试让当前最需要帮助的人（钱最少）和最能提供帮助的人（钱最多）组队。我们证明了这个局部最优选择可以导向全局最优解（即最多的队伍数），因为这最高效地利用了“富裕”朋友的资源。
双指针 (Two Pointers) 双指针是一种非常高效的技巧，通常用在有序数组上。它通过维护两个指针（比如一个在头一个在尾），并根据特定条件移动它们来遍历数组，从而在 O(n) 的时间复杂度内解决问题。在这里，我们将差值数组排序后，一个指针 l 从左向右移动，一个指针 r 从右向左移动。它们共同协作，以线性的时间复杂度完成了所有可能的“最优配对”的检查。相比于 O(n^2) 的暴力枚举所有配对，双指针的效率要高得多得多！

好啦，这道题的讲解就到这里啦！希望能帮到主人喵~ ( ´ ▽ ` )ﾉ

题目大意 ​

解题思路 ​

题解代码 ​

知识点介绍 ​

题目大意

解题思路

题解代码

知识点介绍