博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
ZOJ 1076 Gene Assembly
阅读量:6419 次
发布时间:2019-06-23

本文共 1119 字,大约阅读时间需要 3 分钟。

  题目大意:选择不相交区间问题。给定n个区间(a,b),选择尽可能多的区间,是的这些区间两两不相交。

  经典贪心问题,将区间按照上界进行排序,选择第一个区间,然后去掉与第一个区间相交的区间,以此类推。

1 #include 
2 #include
3 using namespace std; 4 #define MAXN 1000+10 5 6 struct Interval 7 { 8 int l, r, num; 9 bool operator < (const Interval& x) const10 {11 return r < x.r;12 }13 };14 Interval interval[MAXN];15 16 int main()17 {18 #ifdef LOCAL19 freopen("in", "r", stdin);20 #endif21 int n;22 while (scanf("%d", &n) != EOF && n)23 {24 for (int i = 0; i < n; i++)25 {26 scanf("%d%d", &interval[i].l, &interval[i].r);27 interval[i].num = i + 1;28 }29 sort(interval, interval+n);30 int start = interval[0].r;31 printf("%d", interval[0].num);32 for (int i = 0; i < n; i++)33 if (interval[i].l > start)34 {35 start = interval[i].r;36 printf(" %d", interval[i].num);37 }38 printf("\n");39 }40 return 0;41 }
View Code

 

转载于:https://www.cnblogs.com/xiaobaibuhei/p/3258577.html

你可能感兴趣的文章
弹窗 组件 封装
查看>>
[Widget] HTML5解决跨域问题
查看>>
Uva 1451
查看>>
python基础一 ------"有序"的字典
查看>>
JS为句柄添加监听函数
查看>>
[导入]WAP编程(性能篇)
查看>>
curl 发送get post请求
查看>>
linux介绍
查看>>
JS 用sort方法排序字符串
查看>>
phpstrom调试神器
查看>>
Windows下磁盘无损重新分配
查看>>
实践:VIM深入研究(20135301 && 20135337)
查看>>
Shell 流程控制
查看>>
mongodb配置
查看>>
多客户端项目的冗余服务器
查看>>
如何把session保存在mysql中?
查看>>
error C2872: “ACCESS_MASK”: 不明确的符号
查看>>
第10周作业
查看>>
hdu 1556 Color the ball (树状数组)
查看>>
POJ 2513 Colored Sticks【欧拉通路】
查看>>