题解：CF1462F The Treasure of The Segments

skimlight · 2026-08-10 21:58:48 · 题解

题意

给出 n 条线段 [l_i,r_i]，你可以删除其中若干条，要求删除后剩下的线段中存在一条线段，与其余所有线段都有交点（端点也算）。问最少删除几条线段。

暴力

我们最终要保留一个非空集合。这个集合里必须至少有一条“特殊线段”，它和集合里其他线段都相交。

如果我们提前选定了这条特殊线段，那么为了满足条件，所有与这条特殊线段不相交的线段都必须被删掉，而与它相交的线段可以全部留下。

所以，对于某条特殊线段 [L,R]，最少删除数 = 原数组中与 [L,R] 不相交的线段数量。因此，枚举每条线段作为特殊线段，并统计与其不相交的区间数，答案取最小值。

时间复杂度 O(n^2)。

正解思路

给定线段 [L,R]，另一条线段 [l,r] 与它不相交，只有两种情况：

1. 完全在左边：整条线段在 [L,R] 的左侧，即 r<L。
2. 完全在右边：整条线段在 [L,R] 的右侧，即 l>R。

由于不可能同时满足两个条件（因为左右互斥），所以不相交的总数 = 左边数量 + 右边数量。

左边数量 = 所有线段中，满足 r<L 的线段个数。

• 如果我们把所有线段的右端点 r 收集起来，排好序，那么只需在排序后的右端点数组里二分查找 L，找到第一个 \ge L 的位置 posl，那么 posl 就是右端点小于 L 的个数。

右边数量 = 所有线段中，满足 l>R 的线段个数。

• 收集所有左端点 l 排好序，二分查找 R，找到最后一个 \le R 的位置 posr，那么从 posr+1 到末尾都是左端点大于 R 的，个数 =n-(posr+1)。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
struct Node{
    int l, r;
}a[N];
int n, l[N], r[N];
void Solve() {
    cin >> n;
    for (int i = 1; i <= n; ++ i) {
        cin >> a[i].l >> a[i].r;
        l[i] = a[i].l, r[i] = a[i].r;
    }
    sort(l + 1, l + n + 1);
    sort(r + 1, r + n + 1);
    int cnt = n;
    for (int i = 1; i <= n; ++ i) {
        int pos1 = lower_bound(r + 1, r + n + 1, a[i].l) - r - 1;//最后一个小于
        int pos2 = upper_bound(l + 1, l + n + 1, a[i].r) - l;//第一个大于
        pos2 = n - pos2 + 1;
        cnt = min(cnt, pos2 + pos1);
    }
    cout << cnt << '\n';
}
int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int T;
    cin >> T;
    while (T --) {
        Solve();
    }
    return 0;
}