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 ;
}

最新文章

  1. java.lang.ClassNotFoundException: com.mysql.jdbc.Driver解决办法
  2. GridLookUpEdit多列模糊查询最简单方式 z
  3. sprint3(第八天)
  4. android游戏动画特效的一些处理
  5. 异常处理:Sys.WebForms.PageRequestManagerParserErrorException:The message……
  6. CSS计数器与动态计数呈现
  7. ios7新增基础类库以及OC新特性
  8. yum使用详细
  9. HDU 3401 Trade(单调队列优化)
  10. Glyphicons 字体图标
  11. RxSwift学习笔记7:buffer/window/map/flatMap/flatMapLatest/flatMapFirst/concatMap/scan/groupBy
  12. VS2015企业版专业版密钥
  13. scanf的一个问题(暂未解决)
  14. Codeforces 138C Mushroom Gnomes - 2 线段树
  15. Liferay7.0与cas单点登录配置
  16. appium通过同级别(兄弟关系)元素找到元素
  17. PULL解析学习
  18. 02-分页器,自定义分页器,解耦函数分页器,分页器class
  19. codeforces 722E Research Rover
  20. JavaWeb(十七)——JSP中的九个内置对象

热门文章

  1. 两个同名controller导致调用崩溃
  2. 二维码彩色广告招牌的切割制作问题(C#.net下对彩色二维码圆角样式及改进)
  3. WPF Dispatcher的使用
  4. delphi备份恢复剪切板(使用了GlobalLock API函数和CopyMemory)
  5. 【C#】list 去重
  6. Windows 10开发基础——指针事件和操作事件(一)
  7. dotnet core 跨平台编译发布
  8. 遍历所有的XML
  9. VC 使用msxml6.dll动态链接库中的函数读写XML文件
  10. VC 调用 MinGW 生成的dll good