CF1249D2 Too Many Segments (hard version)

洛谷链接

思路

区间覆盖问题，又是求最小的删除个数，可以想到是贪心。

我们按顺序考虑，假设当前点 $1 \cdots i-1$ 都已经合法，目前要处理不合法的 $i$。

那么在当前所有覆盖着点 $i$ 的线段中，自然要不断选择右端点最大的线段进行删除，直到点 $i$ 合法。

正确性也不难证明：前 $i-1$ 个点已经合法，不用考虑，选择右端点最大的线段对于其它决策具有决策包容性。

那么我们只需要先将所有线段按左端点排序，在遍历到点 $i$ 的时候将可以覆盖点 $i$ 的线段放入大根堆中。

其中大根堆以右端点大为优先级更高，然后当点 $i$ 不合法时，不断取出堆顶，删除该线段。如此往复知道遍历结束即可。

代码：

 

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <queue>
 5 #include <vector>
 6 #include <utility>
 7 using namespace std;
 8 const int maxn = 200005;
 9 int sum[maxn],n,k;
10 struct segment {
11     int l,r,id;
12     segment() {
13         l = r = id = 0;
14     }
15     segment(int l,int r):l(l),r(r){}
16     bool operator < (const segment& p)const {
17         return r < p.r;
18     }
19 }a[maxn];
20 bool cmp(segment x,segment y) {
21     return (x.l ^ y.l) ? x.l < y.l : x.r < y.r;
22 }
23 priority_queue<segment> q;
24 vector<int> ans;
25 int main() {
26     scanf("%d%d",&n,&k);
27     for(int i = 1;i <= n;++ i)scanf("%d%d",&a[i].l,&a[i].r),a[i].id = i,++ sum[a[i].l],-- sum[a[i].r + 1];
28     sort(a + 1 , a + 1 + n , cmp);
29     int j = 1;
30     int cnt = 0;
31     for(int i = a[1].l;i <= a[n].r;++ i) {
32         for(;j <= n&&a[j].l <= i;++ j)q.push(a[j]);
33         sum[i] += sum[i - 1];
34         while(sum[i] > k) {
35             segment w = q.top();
36             q.pop();
37             -- sum[i];
38             ++ sum[w.r + 1];
39             ans.push_back(w.id);
40         }
41     }
42     printf("%d\n",ans.size());
43     sort(ans.begin() , ans.end());
44     for(int i = 0;i < ans.size();++ i)printf("%d ",ans[i]);
45     return 0;
46 } 

QAQ