【DS思想+堆贪心】CF595div3 D2

阳光穿透心脏的1/2处 2024-03-04 07:40 101阅读 0赞

[Problem - D2 - Codeforces][]

题意：

![4ded56b6d89346f282ac8fb7d8414893.png][]

![27da294e50c34914ab443184834b0f1c.png][]

思路：

大家都说这是典，但是我不懂怎么个典法，可能堆贪心都是这样做的吗，不懂

首先肯定要贪心，对于一个坏点，优先删除覆盖别的点多的

考虑nlogn做法，先去枚举点，然后把覆盖该点的所有区间扔进优先队列里，优先删除右端点靠右的

那怎么看是不是坏点，还得维护一个差分数组，边枚举边维护

感觉突破点就是堆贪心

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using i64 = long long;
    
    constexpr int N = 2e5 + 10;
    constexpr int M = 1e6 + 10;
    constexpr int P = 2600;
    constexpr i64 Inf = 1e18;
    constexpr int mod = 998244353;
    constexpr double eps = 1e-6;
    
    struct ty {
        int l, r;
        int id;
        bool operator < (const ty & a) const {
            return a.r > r;
        }
    }p[N];
    
    std::priority_queue<ty> q;
    
    int n, k;
    int sum[N];
    int ans[N];
    
    bool cmp(ty x, ty y) {
        if (x.l == y.l) return x.r < y.r;
        return x.l < y.l;
    }
    void solve() {
        std::cin >> n >> k;
        for (int i = 1; i <= n; i ++) {
            std::cin >> p[i].l >> p[i].r;
            p[i].id = i;
            sum[p[i].l] ++;
            sum[p[i].r + 1] --;
        }
    
        std::sort(p + 1, p + 1 + n, cmp);
    
        int j = 1;
        int len = 0;
        for (int i = 1; i < N; i ++) {
            while (j <= n && p[j].l <= i) q.push(p[j ++]);
            sum[i] += sum[i - 1];
            while (sum[i] > k) {
                auto u = q.top();
                q.pop();
                ans[++len] = u.id;
                sum[i] --;
                sum[u.r + 1] ++;
            }
        }
    
        std::cout << len << "\n";
        for (int i = 1; i <= len; i ++) std::cout << ans[i] << " \n" [i == len];
    }
    signed main() {
        std::ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
        
        int t = 1;
    
        while (t--) {
            solve();
        }
        
        return 0;
    }

[Problem - D2 - Codeforces]: https://codeforces.com/contest/1249/problem/D2
[4ded56b6d89346f282ac8fb7d8414893.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/04/659054cea3ba40c9bbb98c45452e8621.png
[27da294e50c34914ab443184834b0f1c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/04/dd58a1ef5ff74b97b3039ee93a5dbaf0.png