选点问题(贪心算法)
2021/11/24 20:12:56
本文主要是介绍选点问题(贪心算法),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
数轴上有n个闭区间[ai, bi]。取尽量少的点,使得每个区间内都至少有一个点(不同区间内含的点可以是同一个)。
输入格式:
第一行一个数字n,表示有n个闭区间。 下面n行,每行包含2个数字,表示闭区间[ai, bi]
输出格式:
一个整数,表示至少需要几个点
输入样例:
在这里给出一组输入。例如:
3 1 3 2 4 5 6
输出样例:
在这里给出相应的输出。例如:
2
思考过程:
- 如果一个点取在交集内,那么该点所占的区间更多
- 看看三种最基本的情况:
- 那么怎样最可能找到交集呢? 如上图,我们需要将右端点从小到大排序的同时使得在右端点相同的情况下,左端点越大越好(这样更可能优先遇到交集)
- 接下来怎样取点呢?仔细想想,经过上面一番排序之后,我们如果取右端点会使总的点数更少实际操作:设置一个标志位 f,每次将本区间的左端点同标志位作比较,这样是为了考虑要不要增加点(标志位会在本区间的左端点大于 f 的时候更新为本区间的右端点),不理解可以参考上面图一,实际上不管哪种情况增加点都可以简化为图一。
c++代码实现:
#include <iostream> #include <algorithm> using namespace std; struct SEC //每个区间 { int left; int right; }; bool cmp(SEC s1, SEC s2) { if (s1.right == s2.right) return s1.left > s2.left; else return s1.right < s2.right; } int main() { int n, f = -1000000, ans = 0; //f是标志位 cin >> n; SEC sections[n]; for (int i = 0; i < n; i++) { cin >> sections[i].left >> sections[i].right; } sort(sections, sections + n, cmp); //将右端点从小到大排序 for (int i = 0; i < n; i++) { if (sections[i].left > f) //将本区间的左端点和上一区间的右端点作比较 { f = sections[i].right; ans++; } } cout << ans; return 0; }
大家要是觉得有帮助就点个赞吧~
这篇关于选点问题(贪心算法)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-20接口模块封装入门教程
- 2024-09-20请求动作封装入门教程
- 2024-09-20登录鉴权学习:新手入门教程
- 2024-09-20后台管理开发学习:新手入门指南
- 2024-09-20后台管理系统开发学习:从入门到实践
- 2024-09-20后台开发学习:从入门到初级实战指南
- 2024-09-20后台综合解决方案学习:从入门到实践
- 2024-09-20接口模块封装学习入门指南
- 2024-09-20请求动作封装学习:新手入门教程
- 2024-09-20登录鉴权入门:打造安全的用户认证系统