贪心 区间贪心
教程导读
学研发网的这篇信息学奥赛技术教程文章主要介绍了贪心 区间贪心,现在分享给大家,供学习和参考。文章包含1030字,纯文字阅读大概需要3分钟。
教程信息
区间贪心
通过题目解题认识区间贪心
题目内容:
解题思路:
1、按照区间的右端点对区间进行从小到大的排序
2、遍历每一个区间
1)如果这个区间跟前面的区间没有交集,选择这个区间的右端点
2)如果这个区间跟前面的区间有交集,跳过这个区间继续遍历
3、最后选择的点的个数就是答案
实现代码:
#include<iostream> #include<algorithm> using namespace std; const int N = 100010; int n; //定义一个区间结构体 struct Range { int l, r; //重载小于号 bool operator < (const Range & w) const { //根据右端点进行排序 return r < w.r; } } range[N]; int main() { int n; scanf("%d", &n); for (int i = 0; i < n; i++) { int l, r; scanf("%d%d", &l, &r); range[i] = { l, r }; } //排序 sort(range, range + n); //从左到右开始扫描 int res = 0; //当前选中的点的个数 int ed = -2e9; //上一个点的下标 -2000000000 cout<<ed<<endl; //开始枚举所有的区间 for (int i = 0; i < n; i++) { //如果当前这个区间被前面的点所覆盖 //那么一定会被上一个选中的点覆盖, //同理,如果上一个点没有覆盖当前这个区间,则当前这个区间的右端点应该被选上 if (range[i].l > ed) { //如果上一个点没有覆盖当前这个区间 res++; ed = range[i].r; } } printf("%d", res); return 0; }
执行结果:
教程咨询
如果章节内容看不懂,可以联系作者。
教程总结
以上是学研发网为您提供贪心 区间贪心的全部内容,希望教程文章能够帮你了解学习贪心 区间贪心,解决所遇到的问题。 如果觉得学研发网信息学奥赛教程内容还不错,欢迎将学研发网网站推荐给身边需要的人。
教程备注
版权声明:教程内容为学研发网整理和编写,如需转载请联系站长并附上文章原始链接和原始作者信息。
手机阅读
扫描二维码推送至手机访问。
本文链接:http://www.xueyanfa.com/xinaojiaocheng/xinaogaoji-290.html