越来越菜了

题解 #

贪心的策略是：遍历所有点，当我们发现有被超过 $k$ 条线段覆盖的点时，我们应该移除右端点最靠右的线段。

为了实现我们的策略，我们需要一个数组 $open_i$ 来存储以点 $i$ 开始的线段，和数组 $close_i$ 来存储以点 $i$ 结束的线段。我们同时还需要维护覆盖当前点的集合，以及一个优先队列来寻找右端点最右的线段。

具体来说，就是对于每个点，我们先往集合里插入从这个点开始的线段，然后找出应该删除的线段并删除，最后从集合里移除以这个点结束的线段。

Code #

#include <bits/stdc++.h>
 
#define F first
#define S second
#define endl '\n'
using namespace std;
 
const int INF = 0x3f3f3f3f;
typedef long long ll;
typedef pair<int, int> pii;
 
const int N=2e5+5;
vector<pii> open[N];
vector<int> close[N];
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        int l,r;
        cin>>l>>r;
        close[r].emplace_back(i);
        open[l].emplace_back(r,i);
    }
    set<int> now;
    vector<int> ans;
    priority_queue<pii> pq;
    for(int i=1;i<=N-1;i++){
        for(auto it:open[i]){
            now.insert(it.S);
            pq.push(it);
        }
        while(now.size()>k){
            pii tmp=pq.top();
            pq.pop();
            now.erase(tmp.S);
            ans.emplace_back(tmp.S);
        }
        for(int x:close[i]){
            now.erase(x);
        }
    }
    cout<<ans.size()<<endl;
    for(int it:ans) cout<<it<<' ';
    return 0;
}

Codeforces 1249D2 - Too Many Segments (hard version) 题解

题解 #

Code #