#贪心，平衡树#洛谷 3602 Koishi Loves Segments

本文主要是介绍#贪心，平衡树#洛谷 3602 Koishi Loves Segments，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

有$n$个区间，有$m$个限制，第$i$个点不得覆盖超过$t_i$个区间，问最多能保留多少个区间

---

分析

首先对于每个限制进行排序，那按照贪心的思想，首先对区间的开头进行排序，那首先之前没有限制的区间可以删掉了，然后如果不满足，区间的末尾越大，越值得删掉，因为这个区间很有可能继续受到影响，那就是平衡树了，但是我太菜了，只会multiset，时间复杂度$O(m+nlogn)$

---

代码

#include <cstdio>
#include <cctype>
#include <algorithm>
#include <set>
#define rr register
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<13,stdin)),p1==p2?EOF:*p1++)
using namespace std;
struct rec{int x,y;}a[200001],b[400001]; char buf[1<<13],*p1,*p2;
multiset<int>uk; int n,m,ans;
inline signed iut(){rr int ans=0,f=1; rr char c=getchar();while (!isdigit(c)) f=(c=='-')?-f:f,c=getchar();while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();return ans*f;
}
bool cmp(rec a,rec b){return a.x<b.x;}
signed main(){ans=n=iut(),m=iut();for (rr int i=0;i<n;++i) a[i]=(rec){iut(),iut()};for (rr int i=0;i<m;++i) b[i]=(rec){iut(),iut()};sort(a,a+n,cmp),sort(b,b+m,cmp);for(rr int i=0,j=0;i<m;++i){while(j<n&&a[j].x<=b[i].x) uk.insert(a[j++].y);while(uk.size()&&*uk.begin()<b[i].x) uk.erase(uk.begin());while(uk.size()>b[i].y) uk.erase(--uk.end()),--ans;}return !printf("%d",ans);
}

这篇关于#贪心，平衡树#洛谷 3602 Koishi Loves Segments的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---