CF1249D2 Too Many Segments (hard version)

给你条线段，每条线有起始点和终止点，线段会覆盖一个直线上的到的所有点，问你取消多少条线段后可以使每一个点都不被大于的数量的线段覆盖。
## 前置知识
考虑对于第个点，之前的所有点都满足了要求，如果不满足要求，要去掉一些线段，那么肯定是要选右端点最大的，因为左边已经不管了，去掉之后对右边的影响越大越好，这时候时间复杂度是的。

#include<bits/stdc++.h> using namespace std; const int N=2e2+5; struct node{ int l,r,id; }; node a[N]; int n,k,tot,s[N],sum[N]; bool cmp(node x,node y){ if(x.r==y.r) return x.l<y.l; return x.r<y.r; } int main(){ scanf("%d%d",&n,&k); for(int i=1;i<=n;i++){ scanf("%d%d",&a[i].l,&a[i].r); a[i].id=i; } sort(a+1,a+n+1,cmp); for(int i=1;i<=n;i++){ for(int j=a[i].l;j<=a[i].r;j++){ sum[j]++; if(sum[j]>k){ s[++tot]=a[i].id; break; } } } printf("%d\n",tot); for(int i=1;i<=tot;i++){ printf("%d ",s[i]); } return ~(-1); }

做法
对于的情况，我们可以用优先队列优化，然后模拟也是一样的。

#include<bits/stdc++.h> using namespace std; #define int long long const int N=2e5+5; struct node{ int l,r,id; }; node a[N]; bool cmp(node x,node y){ return x.l<y.l; } struct cmp_r { bool operator()(const node &a, const node &b) const { return a.r < b.r; } }; int n,k,now=1,res=0,d[N]; priority_queue<node,vector<node>,cmp_r> q; vector<int> ans; signed main(){ scanf("%lld%lld",&n,&k); for(int i=1;i<=n;i++){ scanf("%lld%lld",&a[i].l,&a[i].r); a[i].id=i; d[a[i].l]++; d[a[i].r+1]--; } sort(a+1,a+n+1,cmp); for(int i=1;i<=N-5;i++){ d[i]+=d[i-1]; while(now<=n&&a[now].l<=i){ q.push(a[now]); now++; } while(d[i]>k&&!q.empty()){ node p=q.top(); q.pop(); d[i]--; d[p.r+1]++; res++; ans.push_back(p.id); } } printf("%lld\n",res); for(int i=0;i<res;i++) printf("%lld ",ans[i]); return 0;