[CF1249D] Too Many Segments

给定 (n) 条线段，要求去掉最少的线段，使得任意一个整数点被覆盖的次数都不超过 (k)

Solution

先离散化，考虑贪心，按左端点排序，依次扫描，每遇到一个区间就加入堆，堆按右端点大顶，如果当前位置重数 (>k)，就从堆中取出右端点最大的区间删除即可

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 400005;

struct range {
    int l,r,id;
    bool operator < (const range &b) const {
        return r<b.r;
    }
} a[N];

int n,k,u[N];
vector <int> vl[N],vr[N];
map<int,int> mp;

signed main() {
    ios::sync_with_stdio(false);
    cin>>n>>k;
    for(int i=1;i<=n;i++) {
        cin>>a[i].l>>a[i].r;
        mp[a[i].l]++;
        mp[a[i].r]++;
    }
    int ind=0;
    for(auto i=mp.begin();i!=mp.end();i++) i->second=++ind;
    for(int i=1;i<=n;i++) {
        a[i].l=mp[a[i].l];
        a[i].r=mp[a[i].r];
        a[i].id=i;
        vl[a[i].l].push_back(i);
        vr[a[i].r].push_back(i);
    }
    int cnt=0;
    priority_queue <range> q;
    vector <int> ans;
    for(int i=1;i<=ind;i++) {
        for(int j:vl[i]) if(u[j]==0) u[j]=1, ++cnt, q.push(a[j]);
        while(cnt>k) {
            int p=q.top().id; q.pop();
            if(u[p]) {
                u[p]=0;
                --cnt;
                ans.push_back(p);
            }
        }
        for(int j:vr[i]) if(u[j]==1) u[j]=0, --cnt;
    }
    cout<<ans.size()<<endl;
    for(int i:ans) cout<<i<<" ";
}