Codeforces Round #595 (Div. 3)D1D2 贪心 STL

2019-11-06 16:00:49来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

一道用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;
}

原题链接:https://codeforces.com/contest/1249/problem/D2

关于迭代器的tip

 

 


原文链接:https://www.cnblogs.com/ilikeeatfish/p/11808577.html
如有疑问请与原作者联系

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:bit(比特)与Byte(字节)的区别与关系

下一篇:循环优先级队列