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