Koishi Loves Segments

洛咕

题意:给定\(n(n<=2e5)\)条线段的左右端点,给定\(m(m<=4e5)\)个点的位置以及最多能够接受被多少条线段覆盖,求最多能在数轴上放多少条线段?一个点有多个要求时,满足最小要求.

分析:贪心.把线段按照左端点从小到大排序,\(m\)个点也从小到大排序,然后从左往右扫描每个点,把所有左端点在该点左侧的线段的右端点都插入\(multiset\)中,并把右端点在该点左侧的线段从\(multiset\)中删掉,然后如果当前\(multiset\)中的元素个数超过了该点能够接受的范围,则把最大的右端点删掉(这就是本题的贪心策略,因为最大的右端点能够对后面产生的影响是最大的).

因为可能多条线段的右端点一样,所以需要用可重集合\(multiset\).

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
    int x=0,o=1;char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')o=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*o;
}
const int N=2e5+5;
struct node{
    int x,y;
    bool operator <(const node &p)const{
        return x==p.x?y<p.y:x<p.x;
    }
}a[N],b[N<<1];
multiset<int>s;
int main(){
    int n=read(),m=read(),ans=0;
    for(int i=1;i<=n;++i)a[i].x=read(),a[i].y=read();
    for(int i=1;i<=m;++i)b[i].x=read(),b[i].y=read();
    sort(a+1,a+n+1);sort(b+1,b+m+1);
    for(int i=1,j=1;i<=m;++i){
        while(j<=n&&a[j].x<=b[i].x)s.insert(a[j].y),++j;
        while(s.size()&&*s.begin()<b[i].x)s.erase(s.begin());
        while(s.size()>b[i].y)s.erase(--s.end()),++ans;
    }
    printf("%d\n",n-ans);
    return 0;
}

Koishi Loves Segments

原文：https://www.cnblogs.com/PPXppx/p/11743891.html