【DS思想+堆贪心】CF595div3 D2

Problem - D2 - Codeforces

题意：

 

 思路：

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

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

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

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

感觉突破点就是堆贪心

Code：

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