ZOJ 3953:Intervals(优先队列+思维)
2024-09-01 00:08:23
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5572
题意:给出n个线段,问最少删除几个线段可以使得任意一个点不会被三个以上的线段覆盖。
思路:首先离散化坐标。
然后想着按右端点从小到大排序后直接O(n)扫的贪心,但是后面发现错误了。
应该按左端点从小到大排序,然后用一个优先队列(按右端点从大到小排序)。
开始扫坐标,当有与该坐标相同的点的左端点就进队,用ed[]记录右端点的位置。
用cnt记录当前这个点有多少个区间覆盖,当cnt>=3的时候就出队更新。
#include <bits/stdc++.h>
using namespace std;
#define N 50010
struct node {
int l, r, id;
node () {}
node (int l, int r, int id) : l(l), r(r), id(id) {}
bool operator < (const node &rhs) const {
if(r != rhs.r) return r < rhs.r;
return l < rhs.l;
}
} seg[N];
vector<int> ans;
priority_queue<node> que;
int ed[N*], p[N*];
bool cmp(const node &a, const node &b) {
if(a.l != b.l) return a.l < b.l;
return a.r < b.r;
}
int main() {
int t; scanf("%d", &t);
while(t--) {
int n, u, v; scanf("%d", &n);
ans.clear(); memset(ed, , sizeof(ed));
while(!que.empty()) que.pop();
int cnt = , now = , num = ;
for(int i = ; i < n; i++) scanf("%d%d", &u, &v), seg[i] = node(u, v, i + ), p[cnt++] = u, p[cnt++] = v;
sort(seg, seg + n, cmp); sort(p, p + cnt);
cnt = unique(p, p + cnt) - p;
for(int i = ; i < n; i++)
seg[i].l = lower_bound(p, p + cnt, seg[i].l) - p,
seg[i].r = lower_bound(p, p + cnt, seg[i].r) - p; for(int i = ; i < cnt && now < n; i++) {
while(seg[now].l == i && now < n) {
num++;
ed[seg[now].r + ]++; // 线段的终点
que.push(seg[now++]);
}
num -= ed[i]; // 离开了某线段的范围
while(num >= ) {
node tmp = que.top(); que.pop();
num--; ed[tmp.r + ]--; // 这个线段被删除
ans.push_back(tmp.id);
}
}
printf("%d\n", ans.size()); sort(ans.begin(), ans.end());
for(int i = ; i < ans.size(); i++) printf("%d%c", ans[i], i + == ans.size() ? '\n' : ' ');
}
return ;
}
最新文章
- java.lang.ClassNotFoundException: com.mysql.jdbc.Driver解决办法
- GridLookUpEdit多列模糊查询最简单方式 z
- sprint3(第八天)
- android游戏动画特效的一些处理
- 异常处理:Sys.WebForms.PageRequestManagerParserErrorException:The message……
- CSS计数器与动态计数呈现
- ios7新增基础类库以及OC新特性
- yum使用详细
- HDU 3401 Trade(单调队列优化)
- Glyphicons 字体图标
- RxSwift学习笔记7:buffer/window/map/flatMap/flatMapLatest/flatMapFirst/concatMap/scan/groupBy
- VS2015企业版专业版密钥
- scanf的一个问题(暂未解决)
- Codeforces 138C Mushroom Gnomes - 2 线段树
- Liferay7.0与cas单点登录配置
- appium通过同级别(兄弟关系)元素找到元素
- PULL解析学习
- 02-分页器,自定义分页器,解耦函数分页器,分页器class
- codeforces 722E Research Rover
- JavaWeb(十七)——JSP中的九个内置对象