C. Keshi Is Throwing a Party - 题解

比赛与标签

比赛: Codeforces Global Round 17 标签: binary search, greedy 难度: *1600

派对开始啦！—— 题目大意喵

喵~ 主人 sama，Keshi 要开一个盛大的派对，他有 n 个朋友，编号从 1 到 n。非常有趣的是，第 i 个朋友恰好有 i 块钱，所以他们的财富是按编号递增的哦！

Keshi 想邀请尽可能多的朋友来参加派对，但每个朋友都有点小脾气呐。对于第 i 个朋友，他只有在满足以下两个条件时才会开心：

1. 派对里，比他有钱的人数不能超过 a_i 个。
2. 派对里，比他没钱的人数不能超过 b_i 个。

我们的任务就是，找出一种邀请方案，使得被邀请的每一个人都很开心，并且总人数最多！请你告诉 Keshi，他最多能邀请多少人呢？

喵呜~ 解题思路分析

这个问题问的是“最多”能邀请多少人，这种“最大化某个值”的问题，常常可以转换成一个判定性问题来解决，这可是二分答案的经典信号哦，喵！

为什么能二分答案？

我们可以二分最终能邀请的人数，比如说 x。然后，我们需要一个 check(x) 函数来判断：“我们到底能不能邀请到 x 个让所有人都开心的朋友呢？”

想想看，如果我们能成功邀请 x 个人，那少邀请一个，只邀请 x-1 个人，肯定也办得到呀（只要从那 x 个人里随便去掉一个，剩下的人只会更开心，因为比他们有钱或没钱的人数只可能减少或不变）。所以这个答案是具有单调性的，二分搜索完全没问题！

check(x) 函数的贪心策略

好~现在最关键的就是怎么写 check(x) 函数了。假设我们决定要邀请 x 个人，我们应该优先邀请谁呢？

一个很自然的想法是，我们从最穷的朋友（朋友1）开始，一个个地考虑要不要邀请他们。这是一个贪心的策略，喵~

我们用一个计数器 count 记录当前已经成功邀请了多少人。当我们考虑第 i 个朋友时，如果决定邀请他，他就会成为我们已邀请的 count + 1 个人里，财富排名第 count + 1 的人（因为我们是按财富顺序考虑的）。

那么，对于这个即将被邀请的朋友 i：

• 比他穷的人数，就是我们已经邀请的 count 个人。
• 比他有钱的人数，就是我们总共要邀请 x 个人，减去他自己和比他穷的 count 个人，也就是 x - 1 - count 个人。

所以，要让朋友 i 开心，必须同时满足他的两个要求：

1. count <= b_i (比他穷的人数不能超标)
2. x - 1 - count <= a_i (比他有钱的人数不能超标)

只要朋友 i 满足这两个条件，我们就贪心地邀请他，然后把 count 加一，接着去考虑下一个朋友。如果我们遍历完所有 n 个朋友后，count 最终能达到 x，说明 check(x) 成功，我们确实能找到 x 个开心的朋友，返回 true！否则就说明 x 太大了，办不到，返回 false。

这样，我们的整体思路就清晰啦：

1. 二分答案 mid，范围是 [0, n]。
2. 在 check(mid) 中，使用贪心策略进行验证。
3. 根据 check(mid) 的结果，调整二分的 low 和 high 指针，直到找到最大的可行的 mid。

代码实现喵~

#include <iostream>
#include <vector>
using namespace std;

// check函数，用来判断是否可以邀请 mid 个人参加派对
bool check(int mid, vector<pair<int, int>>& v) {
    // 如果要邀请0个人，当然是可以的啦
    if (mid == 0) 
        return true;
    
    // count 记录当前已经成功邀请的人数
    int count = 0;
    
    // 遍历所有 n 个朋友 (0-indexed, 所以是 0 到 n-1)
    for (int i = 0; i < v.size(); i++) {
        // 如果已经邀请够 mid 个人了，就提前结束，提高效率喵~
        if (count == mid) 
            break;
        
        // v[i].second 是 b_i, v[i].first 是 a_i
        // 已经邀请了 count 个人，他们都比当前第 i+1 个朋友穷
        // 那么需要满足 b_i >= count
        //
        // 假设我们邀请了当前朋友，那么派对总人数是 mid
        // 比他有钱的人数就是 mid - 1 - count
        // 那么需要满足 a_i >= mid - 1 - count
        if (v[i].second >= count && v[i].first >= mid - 1 - count) {
            // 两个条件都满足！太棒了，邀请他！
            count++;
        }
    }
    
    // 如果最后成功邀请的人数达到了 mid，说明这个方案可行
    return count >= mid;
}

int main() {
    // 加速输入输出，让程序跑得飞快~
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<pair<int, int>> friends(n);
        for (int i = 0; i < n; i++) {
            // 读取 a_i 和 b_i
            cin >> friends[i].first >> friends[i].second;
        }
        
        // 二分查找答案
        int low = 0, high = n;
        while (low <= high) {
            int mid = low + (high - low) / 2; // 防止溢出的写法
            if (check(mid, friends)) {
                // 如果 mid 个人可以邀请，说明答案可能更大，往右边找
                low = mid + 1;
            } else {
                // 如果 mid 个人不行，说明 mid 太大了，往左边找
                high = mid - 1;
            }
        }
        
        // 当循环结束时, high 就是满足条件的最大人数
        cout << high << '\n';
    }
    return 0;
}

复杂度分析的说

• 时间复杂度: O(N log N) 的说。 二分答案的范围是 [0, n]，所以二分本身需要 O(log n) 次。每次二分我们都要调用 check(x) 函数，这个函数会遍历所有 n 个朋友，所以它的复杂度是 O(n)。因此，总的时间复杂度就是 O(n log n) 啦，对于 n 最大 2 * 10^5 的数据完全足够了喵~

• 空间复杂度: O(N) 的说。 我们主要用了一个 vector 来存储 n 个朋友的信息，所以空间复杂度是 O(n)。

知识点与总结喵

这道题真是太棒了，完美地结合了 二分答案 和 贪心 两种思想，喵~

1. 二分答案的应用: 当题目要求“最大化最小值”或“最小化最大值”，或者像这题一样“最大化数量”时，如果答案具有单调性，就可以考虑二分答案。这能把一个不好直接求解的最优化问题，转换成一个相对容易的判定性问题。

2. 贪心策略的选择: 在 check 函数中，我们选择从最穷到最富的顺序进行贪心选择。这个顺序是关键！因为它保证了当我们考虑朋友 i 时，已经邀请的 count 个人都比他穷，这样我们才能准确地计算出他需要满足的条件。如果换个顺序，比如从富到穷，逻辑就会变得复杂很多。

3. 编程技巧: 二分的边界要小心哦，low 可以从 0 开始（一个人都不邀请），high 是 n。最后的结果是 high，这是 low = mid + 1 和 high = mid - 1 这种二分查找模板的一个常见结果，主人 sama 可以多练习熟悉一下呐！

希望这篇题解能帮到你，下次遇到类似的问题，也能一眼看穿它的本质！加油，喵~