Codeforces Round #595 (Div. 3)D1D2

ilikeeatfish 2019-11-06 原文

Codeforces Round #595 (Div. 3)D1D2

一道用STL的贪心，正好可以用来学习使用STL库

题目大意：给出n条可以内含，相交，分离的线段，如果重叠条数超过k次则为坏点，n,k<2e5

所以我们贪心的想我们从左往右遍历，如果重合部分条数超过了k，就必须去除线段，（此时从左边看去除线段后不会出现冲突，右边还有剩余很多线段未知）所以我们选择去除这些重合线段里右端最右的部分

实现：

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
const int maxn =2e5+30;
set<pii>res;
vector<pii>v[maxn];
vector<int>ans;
int main(){
int n,k,mx=0,t1,t2;
scanf(“%d%d”,&n,&k);
for(int i=1;i<=n;i++){
scanf(“%d%d”,&t1,&t2);
v[t1].push_back({t2,i});//左端点t1储存右端点和序号i，C11的用法这里{t2,i}等于make_pair
mx=max(t2,mx);
}
for(int i=0;i<=mx;i++){
while(res.begin()->first <i&&!res.empty())//当右端点小于i时已经完全扫过，此时删去该线段
res.erase(res.begin());//删去整条线段
for(int j=0;j<v[i].size();j++)
res.insert(v[i][j]);//插入该端点为左端点下的线段
while(res.size()>k){//如果此时重合部分大于k，则找到这些线段里右端点最右的线段，加入ans并删去
ans.push_back(res.rbegin()->second);//rbegin()返回的是最末元素的位置
res.erase(–res.end());//注意虽然效果一样但end和rbegin的类型不一样
}
}
cout<<ans.size()<<endl;
for(auto x:ans){
cout<<x<<‘ ‘;
}
cout<<endl;
}