NYOJ - 选择不相交区间(贪心)
发布日期:2021-07-01 00:14:50
浏览次数:2
分类:技术文章
本文共 932 字,大约阅读时间需要 3 分钟。
- 内存限制:64MB 时间限制:1000ms
题目描述:
好吧。这道题的目的在于让大家认识贪心问题的三个区间经典问题:区间选点问题,区间覆盖问题,以及该题的选择不相交区间问题。有许多的贪心问题可以转化为这三类的问题。
那么,对于该问题。就是给一系列的区间,求最多的区间,要求区间个数最多,这些区间不相交,需要注意的是这些区间都是闭区间。
输入描述:
第一行一个数n为区间个数(n<=1000)接下来有n行,每行有两个数a,b分别为区间的两个端点,a,b在int范围。EOF结尾。
输出描述:
输出如样例所示。
样例输入:
2
1 10 10 11 3 1 10 10 11 11 20
样例输出:
Case 1:
1. Case 2: 2.
解题思路:
选择不相交区间问题:贪心思想,先按b从小到大进行排序,再选择b0作为选点temp,如果出现ai>temp,则以bi作为temp,再按照这样的方式迭代,直至所有区间遍历完。这道题有点坑,输入的时候要判断两个端点的大小。
#include#include using namespace std;struct edge { int l, r;}e[1010];int cmp(edge a, edge b){ return a.r < b.r;}int main(){ int t = 1, n, ans, temp; while (cin >> n) { ans = 1; for (int i = 0; i < n; i++) { cin >> e[i].l >> e[i].r; if (e[i].l > e[i].r) swap(e[i].l, e[i].r); } sort(e, e + n, cmp); temp = e[0].r; for (int i = 1; i < n; i++) { if (e[i].l > temp) { ans++; temp = e[i].r; } } cout << "Case " << t++ << ":\n" << ans << ".\n"; } return 0;}
转载地址:https://lzyws739307453.blog.csdn.net/article/details/84072294 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
留言是一种美德,欢迎回访!
[***.207.175.100]2024年04月24日 19时05分46秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
JavaDoc---生成自己的API文档
2019-05-01
Java数组详解
2019-05-01
Java面向对象详解
2019-05-01
在Debian 8上使用Apt-Get安装Java
2019-05-01
vs中动态DLL与静态LIB工程中加入版本信息的方法
2019-05-01
大数据分析技术与应用一站式学习(值得收藏)_v20200418
2019-05-01
Qt 在windows下的串口读写
2019-05-01
如何在SpringMVC中配置Atomikos分布式事务
2019-05-01
Spring Boot 注解@EnableAutoConfiguration的解析
2019-05-01
SpringApplication执行流程
2019-05-01
Spring Boot Quartz 动态任务实现方式
2019-05-01
Spring MVC Quartz 动态任务实现方式
2019-05-01
自定义Starter
2019-05-01
Spring Batch 入门之 CSV-to-DB
2019-05-01
日志写入数据库:Log4j2-JDBCAppender
2019-05-01
分布式事务原理探究(一)
2019-05-01
Java 并发学习记录之线程间通信
2019-05-01
Java并发学习记录之volatile
2019-05-01
spring cloud consul 应用的多实例名的解决
2019-05-01