NYOJ - 找点(贪心)
发布日期:2021-07-01 00:14:50
浏览次数:2
分类:技术文章
本文共 879 字,大约阅读时间需要 2 分钟。
- 内存限制:64MB 时间限制:2000ms
题目描述:
上数学课时,老师给了LYH一些闭区间,让他取尽量少的点,使得每个闭区间内至少有一个点。但是这几天LYH太忙了,你们帮帮他吗?
输入描述:
多组测试数据。每组数据先输入一个N,表示有N个闭区间(N≤100)。接下来N行,每行输入两个数a,b(0≤a≤b≤100),表示区间的两个端点。
输出描述:
输出一个整数,表示最少需要找几个点。
样例输入:
4
1 5 2 4 1 4 2 3 3 1 2 3 4 5 6 1 2 2
样例输出:
1
3 1
解题思路:
区间选点问题:贪心思想,先按b从小到大进行排序,再选择b0作为选点temp,如果出现ai>temp,则以bi作为temp,再按照这样的方式迭代,直至所有区间遍历完。
#include#include using namespace std;struct edge { int l, r;}e[110];int cmp(edge a, edge b){ return a.r < b.r;}int main(){ int t, n, ans, temp; while (cin >> n) { ans = 1; for (int i = 0; i < n; i++) cin >> 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 << ans << endl; } return 0;}
转载地址:https://lzyws739307453.blog.csdn.net/article/details/84072218 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
很好
[***.229.124.182]2024年04月11日 14时42分55秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
Request_继承体系
2019-05-01
前端权限控制:获取用户信息接口构造数据
2019-05-01
有状态服务和无状态服务
2019-05-01
七牛云存储:断点续传
2019-05-01
字节流复制文本文件【应用】
2019-05-01
字节流复制图片
2019-05-01
其他数字摘要算法实现
2019-05-01
私钥加密私钥解密
2019-05-01
锁的释放流程-ReentrantLock.unlock
2019-05-01
Java判断字符串是否为数字(浮点类型也包括)
2019-05-01
Err:11 https://developer.download.nvidia.cn/compute/cuda/repos/ubuntu2004/x86_64 Packages 404 No
2019-05-01
ubuntu opencv-python 安装很慢问题
2019-05-01
MySQL5.7版本修改了my.ini配置文件后mysql服务无法启动问题
2019-05-01
【大数据开发】Java基础 -总结21-Hashmap和HashTable的区别
2019-05-01
Azkaban体系结构
2019-05-01
机器学习之重头戏-特征预处理
2019-05-01
synchronized底层实现及锁的升级、降级
2019-05-01
PermGen space-永久区内存溢出
2019-05-01