Codeforces Round #595 (Div. 3)D1D2 贪心 STL
2019-11-06 16:00:49来源:博客园 阅读 ()
一道用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
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
下一篇:循环优先级队列
- CodeForces 1326E - Bombs 2020-03-25
- CodeForces 1320D - Reachable Strings 2020-03-20
- CodeForces 1324 - Codeforces Round #627 (Div. 3) 2020-03-13
- CodeForces 710D Two Arithmetic Progressions 2020-03-06
- CodeForces 1313D Happy New Year 2020-03-04
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash