题目链接 ---> https://codeforces.com/contest/1249/problem/D2
大致题意：给n条线段，每条线段都覆盖他们所包含的点。问最少删除掉几条线段以至所有点中没有被覆盖的次数大于k的点
题解:遍历每个点，如果某个点被覆盖次数大于k了，那么便将覆盖该点的最长的多余条数删去即可。
#include <cstdio> #include <iostream> #include <algorithm> #include <vector> #include <set> using namespace std; const int mx=2e5+20; struct node{ int y, id; }ans[mx]; vector<node>v[mx]; set<node>s; bool operator < (node a, node b){ if(a.y == b.y) return a.id < b.id; return a.y < b.y; } int a[mx]; int main(){ int n, k; scanf("%d%d",&n,&k); for(int i=1; i<=n; i++){ node t; int a, b; scanf("%d%d",&a,&b); t.id = i; t.y = b; v[a].push_back(t); } int cnt=0; for(int i=1; i<mx; i++){ while(s.size()&&(*s.begin()).y<i) s.erase(*s.begin()); for(int j=0; j<v[i].size(); j++) s.insert(v[i][j]); while(s.size()>k){ ans[++cnt] = *s.rbegin(); s.erase(*s.rbegin()); } } printf("%d\n",cnt); for(int i=1; i<=cnt; i++){ printf("%d%c",ans[i].id,i==cnt?'\n':' '); } return 0; }
