【贪心】CF1841 D

绝地灬酷狼 2024-03-23 23:24 50阅读 0赞

[Codeforces][]

题意：

![f231a62f84944973acc878c8bcd43a09.png][]

![eed5aa21f67e4bf8a27aad529b5370a2.png][]

思路：

首先模拟一下样例

![775c02f6748944878007407ee18918c7.jpeg][]

并没有发现什么

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

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

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

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

问题转化成有多少连通块

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

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

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

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using 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;
    }

[Codeforces]: https://codeforces.com/problemset/problem/1841/D
[f231a62f84944973acc878c8bcd43a09.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/deb51e18de914eefbc830a533e428e41.png
[eed5aa21f67e4bf8a27aad529b5370a2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/acb7321cc88a480c88d89cc14fd8b1b3.png
[775c02f6748944878007407ee18918c7.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/0fbdcdbebebf41b8944886f80739aaa2.png