【贪心】CF1841 D

Codeforces

题意：

思路：

首先模拟一下样例

并没有发现什么

那么就去考虑特殊情况，看看有没有什么启发

考虑一个大区间包含所有小区间的情形，这种情况就是在这么多区间中找出两个区间

换句话说，这么多区间组成一个连通块，在这个连通块中找出两个区间

一个连通块贡献出两个区间

问题转化成有多少连通块

n^2枚举所有区间对，每对区间合并成一个新区间，这个新区间就是一个连通块

问题就变成在这些新区间中找最多的不相交的区间的区间个数

这个就是典，把所有新区间按 r 排序，贪心地选即可

Code：

#include <bits/stdc++.h>#define int long longusing i64 = long long;constexpr int N = 2e5 + 10;
constexpr int M = 4e6 + 10;
constexpr int mod = 998244353;struct ty {int l, r;
}a[N], b[M];int n;bool check(ty x, ty y) {return (y.l >= x.l && y.l <= x.r) || (x.l >= y.l && x.l <= y.r);
}
bool cmp(ty x, ty y) {return x.r < y.r;
}
void solve() {std::cin >> n;for (int i = 1; i <= n; i ++) {std::cin >> a[i].l >> a[i].r; }int tot = 0;for (int i = 1; i <= n; i ++) {for (int j = i + 1; j <= n; j ++) {if (check(a[i], a[j]) || check(a[j], a[i])) {b[++tot] = {std::min(a[i].l, a[j].l), std::max(a[i].r, a[j].r)};}}}if (tot == 0) {std::cout << n << "\n";return;}std::sort(b + 1, b + 1 + tot, cmp);ty t = b[1];int ans = 1;for (int i = 2; i <= tot; i ++) {if ( !check(t, b[i]) && !check(b[i], t)) {ans ++;t = b[i];}}std::cout << n - 2 * ans << "\n";
}signed main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int t = 1;std::cin >> t;while (t--) {solve();}return 0;
}