P1803 凌乱的yyy / 线段覆盖（贪心）

本文主要是介绍P1803 凌乱的yyy / 线段覆盖（贪心），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

思路：

这道题让求区间覆盖，它要求只能一个一个的区间，先对n个区间进行排序，按照区间的结束点前后进行排序。所以从后往前看结束时间点，如果下一个的起点在前一个的结束点之后，则数量加1。

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>using namespace std;struct node
{int s,e;
};
node a[1000010];
int cnt=1;
int n;bool cmp(node aa,node bb)
{return aa.e<bb.e;
}int main()
{cin>>n;for(int i=0;i<n;i++)cin>>a[i].s>>a[i].e;sort(a,a+n,cmp);int p=a[0].e;//第一段不用看，从1开始加 for(int i=1;i<n;i++){if(a[i].s >= p){cnt++;p=a[i].e;}}cout<<cnt;return 0;
}

结果：

这篇关于P1803 凌乱的yyy / 线段覆盖（贪心）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---