F. The Treasure of The Segments - 题解

比赛与标签

比赛: Codeforces Round 690 (Div. 3) 标签: binary search, data structures, greedy, *1800 难度: *1800

题目大意喵~

你好呀，指挥官！Polycarp 在街上捡到了一堆宝藏——n 个线段的说！每个线段都有一个左端点 l 和一个右端点 r。

但是线段太多啦，他想扔掉一些。一个线段集合如果被称为“好”的，需要满足一个条件：集合里存在一个“万能”线段，它能和集合里所有的线段都有交集（哪怕只交于一个点也算哦）。

我们的任务就是，帮 Polycarp 算一算，最少需要扔掉多少个线段，才能让剩下的线段集合变成一个“好”的集合呢？

简单来说，就是：

输入：t 组测试数据。每组数据有一个整数 n，接下来 n 行，每行是线段的 l 和 r。
输出：对于每组数据，输出一个整数，表示最少需要删除的线段数量。

解题思路喵~

这个问题看起来是要我们找到一个最优的子集，直接想可能会有点复杂，喵~。但我们可以换个角度思考一下！

题目要求我们最小化删除的数量，这其实就等价于最大化保留的数量，对吧？而我们保留的线段必须形成一个“好”的集合。

一个“好”的集合的核心在于那个“万能”线段，我们就叫它“主线段”好了。只要我们确定了主线段，那么所有能保留下来的线段，就必须是那些和这个主线段有交集的线段。

这给了我们一个绝妙的思路，呐！我们最初有 n 个线段，最终保留的集合里的主线段，也一定来自于这 n 个线段中的一个。

所以，我们可以这样做：

枚举主线段：我们遍历每一个原始线段 [l_i, r_i]，假设它就是我们最终要找的那个“主线段”。
计算代价：如果 [l_i, r_i] 是主线段，那么所有和它没有交集的线段都必须被删除。我们的目标就是计算出，对于这个假设，需要删除多少个线段。
找到最优解：我们对所有 n 个线段都当一次主线段进行计算，然后取所有计算结果中“需要删除的数量”的最小值，就是最终答案啦！

那么，关键问题来了：对于一个确定的主线段 [l_i, r_i]，如何快速计算出有多少个线段和它没有交集呢？

一个线段 [l_j, r_j] 和 [l_i, r_i] 没有交集，只有两种情况：

[l_j, r_j] 完全在 [l_i, r_i] 的左边，也就是 r_j < l_i。
[l_j, r_j] 完全在 [l_i, r_i] 的右边，也就是 l_j > r_i。

如果我们每次都遍历其他 n-1 个线段来检查，那么总复杂度会是 O(n^2)，这对于 n 达到 2 * 10^5 的数据规模来说，是肯定会超时的说！

这时候，就需要我们的加速魔法——排序和二分查找！

我们可以把所有线段的左端点 l 和右端点 r 分别存到两个数组里，然后对这两个数组进行排序。

l_sorted: 存放所有左端点的排序后数组。
r_sorted: 存放所有右端点的排序后数组。

现在，对于我们选定的主线段 [l_i, r_i]：

要计算有多少个线段满足 r_j < l_i，我们可以在 r_sorted 数组中进行二分查找。具体来说，我们可以用 lower_bound 找到第一个大于等于 l_i 的 r 值的位置。在这个位置之前的所有 r 值，都是小于 l_i 的。这个数量就是我们要找的。
要计算有多少个线段满足 l_j > r_i，我们可以在 l_sorted 数组中进行二分查找。具体来说，我们可以用 upper_bound 找到第一个严格大于 r_i 的 l 值的位置。从这个位置到数组末尾的所有 l 值，都是大于 r_i 的。这个数量也就算出来了。

把这两个数量加起来，就是当我们选择 [l_i, r_i] 作为主线段时，需要删除的线段总数。

我们对每个 i (从 1 到 n) 都执行一次这个 O(log n) 的计算，总的时间复杂度就是 O(n log n)，非常高效，喵~！

代码实现喵~

cpp

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

// 解决单个测试用例的函数喵~
void solve() {
    int n;
    std::cin >> n;
    std::vector<std::pair<int, int>> segments(n);
    std::vector<int> l(n), r(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> segments[i].first >> segments[i].second;
        l[i] = segments[i].first;
        r[i] = segments[i].second;
    }

    // 如果只有0或1个线段，那它本身就是个“好”集合，不需要删除任何东西的说
    if (n <= 1) {
        std::cout << 0 << "\n";
        return;
    }

    // 分别对左端点和右端点进行排序，这是我们高效计算的关键！
    std::sort(l.begin(), l.end());
    std::sort(r.begin(), r.end());

    // 初始化最少删除数量为一个比较大的值
    // 最坏的情况是只保留1个线段，需要删除 n-1 个
    int min_deleted = n - 1;

    // 遍历每一个线段，把它当作可能的“主线段”来尝试
    for (int i = 0; i < n; ++i) {
        int current_l = segments[i].first;
        int current_r = segments[i].second;

        // 需要删除的线段，就是那些和当前主线段候补 [current_l, current_r] 不相交的线段
        // 一个线段 [l_j, r_j] 不相交，意味着：
        // 1. 它完全在左边： r_j < current_l
        // 2. 它完全在右边： l_j > current_r

        // (1) 统计完全在左边的线段数量
        // 在排好序的右端点数组 `r` 中，查找第一个不小于 `current_l` 的元素
        // 这就是 std::lower_bound 的工作。在它之前的所有元素都满足 r_j < current_l
        auto it_left = std::lower_bound(r.begin(), r.end(), current_l);
        int count_left = std::distance(r.begin(), it_left);

        // (2) 统计完全在右边的线段数量
        // 在排好序的左端点数组 `l` 中，查找第一个严格大于 `current_r` 的元素
        // 这就是 std::upper_bound 的工作。从它开始到结尾的所有元素都满足 l_j > current_r
        auto it_right = std::upper_bound(l.begin(), l.end(), current_r);
        int count_right = std::distance(it_right, l.end());

        // 对于当前这个主线段候补，总共需要删除的线段数就是这两部分之和
        int deleted = count_left + count_right;
        
        // 更新我们找到的全局最小删除数
        if (deleted < min_deleted) {
            min_deleted = deleted;
        }
    }

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

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

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

    return 0;
}

复杂度分析喵~

时间复杂度: O(N log N) 的说。
- 首先，我们需要对左端点数组和右端点数组进行排序，这需要 O(N log N) 的时间。
- 接着，我们有一个循环，会遍历 N 个原始线段中的每一个，把它当作主线段候补。
- 在循环内部，我们使用 std::lower_bound 和 std::upper_bound，这两个函数都是基于二分查找的，所以每次操作的时间复杂度是 O(log N)。
- 因此，循环部分的总时间是 O(N * log N)。
- 整体来看，O(N log N) + O(N log N) = O(N log N)，完全可以在规定时间内完成任务，喵！
空间复杂度: O(N) 的说。
- 我们需要存储原始的 n 个线段，这需要 O(N) 的空间。
- 我们还额外创建了两个数组来分别存储所有的左端点和右端点，每个数组的大小都是 N，所以这部分也是 O(N) 的空间。
- 总的空间复杂度就是 O(N)。

知识点与总结喵~

这道题真是一个很好的例子，展示了如何用聪明的思想转换和经典算法来解决问题！

思想转换: 解决问题的关键在于将“最小化删除”转换成“最大化保留”。然后我们意识到，保留的集合必须有一个主线段，这引导我们去枚举主线段。这种“固定一个变量，优化其他变量”的思路在很多题目里都很有用哦！
贪心策略: 我们的整体策略可以看作一种贪心。我们贪心地假设每个线段都有可能成为最终的那个“主线段”，然后计算出基于这个假设的最优情况，最后在所有假设中取最好的一个。
区间问题常用技巧: 对于涉及大量区间判断和计数的问题，将区间的端点（左端点和右端点）分开处理，并对它们进行排序，是一种非常强大和常见的技巧。这能将复杂的二维区间问题，简化成一维的点的问题，从而使用二分查找等高效算法。
C++ STL 的力量: std::sort, std::lower_bound, std::upper_bound 是 C++ 标准库里非常有用的工具，一定要熟练掌握它们呐！特别是 lower_bound（找第一个不小于目标值）和 upper_bound（找第一个大于目标值）的区别，要记清楚哦。

希望这篇题解能帮到你！继续加油，算法的世界里还有更多有趣的宝藏等着我们去发现呢，喵~！

F. The Treasure of The Segments - 题解 ​

比赛与标签 ​

题目大意喵~ ​

解题思路喵~ ​

代码实现喵~ ​

复杂度分析喵~ ​

知识点与总结喵~ ​