F. Mentors - 题解

比赛与标签

比赛: Codeforces Round 481 (Div. 3) 标签: binary search, data structures, implementation 难度: *1500

喵喵，题目在说什么呀？

哈喵~！各位程序员哥哥姐姐们好呀！今天本喵要带大家攻略一道很有趣的题目哦！

题目是这样的：在一个叫做 BerSoft 的公司里，有 n 位程序员，每位程序员 i 都有一个技能值 r_i。一位程序员 a 能成为另一位程序员 b 的导师，需要满足两个条件哦：

a 的技能值必须严格大于 b 的技能值，也就是 r_a > r_b。
a 和 b 之间没有吵过架。

题目会给我们 n 位程序员各自的技能值，还有 k 对吵过架的程序员组合。我们的任务就是，对于每一位程序员，计算出他/她可以成为多少人的导师。最后按输入顺序输出每个人的答案就好啦，喵~

简单来说，就是对每个程序员 i，找出所有技能值比他/她低，并且没有和他/她吵架的程序员数量，是不是很简单呢？

本喵的思路分析时间！

如果我们直接暴力解决，对每个程序员 i，都去遍历其他所有程序员 j，然后检查技能值和吵架关系，那时间复杂度就是 O(n^2) 的说。当 n 达到 2 * 10^5 时，这肯定会超时，电脑会热得可以烤鱼了喵！所以我们需要更聪明的办法！

本喵想到了一个很棒的策略，叫做**“先加后减”**！

第一步：计算理想情况下的导师数量 我们先不管吵架这回事，对于每个程序员 i，我们先计算出有多少人的技能值比 r_i 要低。这不就是他/她潜在可以指导的人数嘛？
怎么快速计算呢？如果技能值数组是无序的，我们还是得一个个比较，很慢的。但是！如果我们把所有人的技能值 r 复制一份，然后排个序得到 r_sorted，事情就变得简单了喵！
对于程序员 i 的技能值 r_i，我们可以在 r_sorted 这个有序数组里，用二分查找（Binary Search）来找到第一个不小于 r_i 的数的位置。那么，在这个位置之前的所有数，就都是严格小于 r_i 的啦！这个位置的下标，就是技能值比 r_i 低的人数！
在 C++ 中，std::lower_bound 这个函数就能完美地帮我们做这件事，它能在 O(log n) 的时间内找到那个位置。所以，我们对 n 个程序员都做一次，总的时间就是 O(n log n)，加上排序的 O(n log n)，非常快！
第二步：减去吵架导致无法指导的人 现在，我们已经有了一个初步的答案数组 ans，ans[i] 表示技能值比程序员 i 低的总人数。但是，这里面包含了一些因为吵架而不能指导的人，我们需要把他们减掉。
我们来处理这 k 对吵架关系。对于每一对吵架的程序员 (u, v)：
- 如果 r_u > r_v，说明 u 本来是可以指导 v 的（因为技能值更高），但因为他们吵架了，所以现在不能了。那么，u 的导师计数 ans[u] 就应该减 1。
- 同理，如果 r_v > r_u，那么 v 的导师计数 ans[v] 就应该减 1。
- 如果 r_u == r_v，他们俩谁也指导不了谁，所以吵不吵架对导师数量没影响，什么都不用做，喵~
我们遍历完所有 k 对吵架关系，并做相应的减法操作后，ans 数组里存的就是最终的正确答案啦！这个过程的时间复杂度是 O(k)。

总结一下本喵的思路： 排序 + 二分查找 O(n log n) + 处理吵架关系 O(k) = 完美AC！

代码魔法，变！

下面就是实现这个思路的魔法代码啦，本喵已经加上了详细的注释，希望能帮到你哟！

cpp

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

int main() {
    // 使用C++标准库的快速IO，让程序跑得更快喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n;
    int k;
    std::cin >> n >> k;

    // r[i] 存储第 i 个程序员的技能值，要保持原始顺序哦
    std::vector<int> r(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> r[i];
    }

    // 创建一个技能值数组的排序副本 r_sorted
    // 这样我们就可以用二分查找来快速计数啦！
    std::vector<int> r_sorted = r;
    std::sort(r_sorted.begin(), r_sorted.end());

    // ans[i] 用来存储第 i 个程序员最终可以指导的人数
    std::vector<int> ans(n);

    // 对于每个程序员，先计算出他/她潜在可以指导的人数
    // 也就是技能值严格低于他/她的人数
    for (int i = 0; i < n; ++i) {
        // 使用 lower_bound 在排序后的数组中查找第一个 >= r[i] 的元素
        // 它前面的所有元素都 < r[i]
        auto it = std::lower_bound(r_sorted.begin(), r_sorted.end(), r[i]);
        // 从开头到这个迭代器的距离，就是技能值比 r[i] 低的人数
        ans[i] = std::distance(r_sorted.begin(), it);
    }

    // 现在来处理 k 对吵架关系
    // 如果一对吵架的人中，一个的技能值高于另一个，那么那个高手的导师计数就要减一
    for (int i = 0; i < k; ++i) {
        int u, v;
        std::cin >> u >> v;
        // 题目给的是1-based索引，我们程序用的是0-based，要转换一下
        --u;
        --v;

        // 如果 u 的技能值比 v 高，那么 u 就不能指导 v 了，计数减一
        if (r[u] > r[v]) {
            ans[u]--;
        } 
        // 反过来，如果 v 的技能值比 u 高，v 就不能指导 u，计数减一
        else if (r[v] > r[u]) {
            ans[v]--;
        }
        // 如果技能值相等，本来就互相不能指导，所以不用管啦
    }

    // 最后，按照原始顺序输出每个程序员的答案
    for (int i = 0; i < n; ++i) {
        std::cout << ans[i] << (i == n - 1 ? "" : " ");
    }
    std::cout << std::endl;

    return 0;
}

效率分析，一点都不能马虎喵~

时间复杂度: O(n log n + k) 的说。
- 读取输入需要 O(n + k) 的时间。
- 复制和排序技能值数组 r，需要 O(n log n) 的时间。
- 对每个程序员使用 lower_bound 计算初始导师数，总共是 n 次，每次 O(log n)，所以是 O(n log n)。
- 处理 k 对吵架关系，循环 k 次，每次都是常数时间操作，所以是 O(k)。
- 整体来看，最耗时的部分是排序和二分查找，所以总时间复杂度是 O(n log n + k)，对于这道题的数据范围来说绰绰有余啦！
空间复杂度: O(n) 的说。
- 我们需要 r 数组存储原始技能值，占用 O(n) 空间。
- r_sorted 数组是 r 的一个拷贝，也占用 O(n) 空间。
- ans 数组用来存储结果，同样是 O(n) 空间。
- 所以总的空间复杂度就是 O(n)，非常节省空间呢！

本喵的小课堂总结~

这道题真是一次愉快的解谜之旅呢！我们来总结一下学到了什么吧，喵~

核心思想 - “先算总数，再减例外”: 这是一个非常实用和常见的解题策略！当直接计算符合所有条件的数量很困难时，可以先放宽条件计算一个总数，然后再减去不符合额外条件的那些。
二分查找的妙用: std::lower_bound 和 std::upper_bound 是 C++ STL 中的强大工具。在有序数组上，它们可以高效地解决“有多少个数小于/大于/等于 x”这类问题。一定要熟练掌握它们哦！
数据备份的重要性: 同时保留原始数据和排序后的数据是一种常见的技巧。原始数据用于保持顺序和对应关系，排序后的数据用于高效查找和计算。
注意细节: 编程时要特别注意题目中的细节，比如本题的“技能值严格大于”和输入的1-based索引，处理不好可是会WA的哦！

希望本喵的题解能帮助你更好地理解这道题！如果还有什么问题，随时可以来问本喵哦！大家一起加油，成为更厉害的程序员吧！喵~ (ฅ'ω'ฅ)

F. Mentors - 题解 ​

比赛与标签 ​

喵喵，题目在说什么呀？ ​

本喵的思路分析时间！ ​

代码魔法，变！ ​

效率分析，一点都不能马虎喵~ ​

本喵的小课堂总结~ ​