本文主要是介绍Codeforces Round #595 (Div. 3) D2 - Too Many Segments (hard version)(贪心)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：https://codeforces.com/contest/1249/problem/D2
题目大意：给出n个线段，问最少删几条边能够使得一个点最多被k条边覆盖
题目思路：比赛的时候一直想着线段树。。然后就歇逼了。。。其实就是个贪心，按照l排序，因为只有在l端点，一个点被覆盖的次数才会增加，所以出事的点一定是左端点。拿个multiset记录在当前点还有哪些边还存活着，存每条边的右端点位置和id。每一轮首先看multiset中最开头的(即右端点小的)，是否比当前枚举到的l还要小，是的话就要删除它，然后插入当前线段的情况。接着看multiset内元素的数量是否大于k，是的话删除r最大的。
以下是代码：
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
const int MAXN = 2e5+5;
const int MOD = 1e9+7;
struct node{int l,r,id;
}a[MAXN];
int n,k;
bool cmp(node a,node b){return a.l<b.l;
}
vector<int>ans;
pair<int,int>p;
multiset<pair<int,int> >s;
int main(){int n,c;ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);while(cin>>n>>k){ans.clear();s.clear();rep(i,1,n){cin>>a[i].l>>a[i].r;a[i].id=i;}sort(a+1,a+n+1,cmp);rep(i,1,n){while(s.size()&&(*s.begin()).first<a[i].l)s.erase(s.begin());p.first=a[i].r,p.second=a[i].id;s.insert(p);while(s.size()>k){auto it=s.end();it--;ans.push_back((*it).second);s.erase(it);}}int len=ans.size();cout<<len<<endl;rep(i,0,len-1){cout<<ans[i]<<" ";}cout<<endl;}return 0;
}
这篇关于Codeforces Round #595 (Div. 3) D2 - Too Many Segments (hard version)(贪心)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
