首页 > 代码库 > ZOJ 3953：Intervals（优先队列+思维）
ZOJ 3953：Intervals（优先队列+思维）
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5572
题意：给出n个线段，问最少删除几个线段可以使得任意一个点不会被三个以上的线段覆盖。
思路：首先离散化坐标。
然后想着按右端点从小到大排序后直接O（n）扫的贪心，但是后面发现错误了。
应该按左端点从小到大排序，然后用一个优先队列（按右端点从大到小排序）。
开始扫坐标，当有与该坐标相同的点的左端点就进队，用ed[]记录右端点的位置。
用cnt记录当前这个点有多少个区间覆盖，当cnt>=3的时候就出队更新。
1 #include <bits/stdc++.h> 2 using namespace std; 3 #define N 50010 4 struct node { 5 int l, r, id; 6 node () {} 7 node (int l, int r, int id) : l(l), r(r), id(id) {} 8 bool operator < (const node &rhs) const { 9 if(r != rhs.r) return r < rhs.r;10 return l < rhs.l;11 }12 } seg[N];13 vector<int> ans;14 priority_queue<node> que;15 int ed[N*2], p[N*2];16 bool cmp(const node &a, const node &b) {17 if(a.l != b.l) return a.l < b.l;18 return a.r < b.r;19 }20 int main() {21 int t; scanf("%d", &t);22 while(t--) {23 int n, u, v; scanf("%d", &n);24 ans.clear(); memset(ed, 0, sizeof(ed));25 while(!que.empty()) que.pop();26 int cnt = 0, now = 0, num = 0;27 for(int i = 0; i < n; i++) scanf("%d%d", &u, &v), seg[i] = node(u, v, i + 1), p[cnt++] = u, p[cnt++] = v;28 sort(seg, seg + n, cmp); sort(p, p + cnt);29 cnt = unique(p, p + cnt) - p;30 for(int i = 0; i < n; i++)31 seg[i].l = lower_bound(p, p + cnt, seg[i].l) - p,32 seg[i].r = lower_bound(p, p + cnt, seg[i].r) - p;33 34 for(int i = 0; i < cnt && now < n; i++) {35 while(seg[now].l == i && now < n) {36 num++;37 ed[seg[now].r + 1]++; // 线段的终点38 que.push(seg[now++]);39 }40 num -= ed[i]; // 离开了某线段的范围41 while(num >= 3) {42 node tmp = que.top(); que.pop();43 num--; ed[tmp.r + 1]--; // 这个线段被删除44 ans.push_back(tmp.id);45 }46 }47 printf("%d\n", ans.size()); sort(ans.begin(), ans.end());48 for(int i = 0; i < ans.size(); i++) printf("%d%c", ans[i], i + 1 == ans.size() ? ‘\n‘ : ‘ ‘);49 }50 return 0;51 }
ZOJ 3953：Intervals（优先队列+思维）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。