P1803 凌乱的yyy/线段覆盖

线段覆盖"/>

P1803 凌乱的yyy/线段覆盖

 这个题主要是让我们在求在有限的时间中最多能参加多少场比赛，也就是贪。

既然比赛是有时间限制的，那么我们便能顺利的想到用时间来排序，求出不冲突的比赛数目，就是答案了。

那么用比赛开始的时间还是比赛结束的时间呢？

 答案很明显是结束时间，因为结束时间早了，开始时间自然不会晚，但是开始时间早了，结束时间可就没办法控制了。所以，按结束时间排序，可以保证我们求到的不冲突的比赛场次就是能够参加的最多的比赛了。

 OK，搞懂了怎么排，那么答案还不明显？？上代码

#include<iostream>
using namespace std;
long long b[100010],e[100010];b开始时间  e：结束时间
int main()
{int n;cin>>n;for(int i=0;i<n;i++){cin>>b[i]>>e[i];}for(int i=0;i<n;i++){for(int j=i+1;j<n;j++){if(e[i]>e[j]){long long t;t=e[j];e[j]=e[i];e[i]=t;t=b[j];b[j]=b[i];b[i]=t;}}}long long j=0;long long num=1;for(int i=1;i<n;i++){if(e[j]<=b[i]){j=i;num++;}}cout<<num<<endl;
}

 我去，居然超时了。

不怕，把cin和cout改成scanf和prinf就行了。

~~~~~改完之后结果一模一样（(ಥ_ಥ) ）

既然不是这个问题，那整个程序最费时间的点莫过于排序了，既然排序麻烦，那就用sort，但是sort好像只能单独排开始时间或者是结束时间吧o(╥﹏╥)o。

所以，就需要用到我们的结构体了(*^▽^*)

先建立一个比赛的结构体，里面int两个变量，分别是起始时间和结束时间

struct acm{int b,e;//b：开始   e：结束
}a[100000];

然后就是解决这道题的重中之重，排序问题，既然要用sort排这个结构体，那就需要再写一个函数来实现咱的自定义排序喽，函数如下：

bool cmp(acm a,acm b)
{return a.e<b.e;//如果a.e<b.e,返回a，否则返回b，实现结构体按照结束时间从小到大排序
}

排序完毕，再找到不冲突的比赛，就是答案喽~

完整代码：

#include<iostream>
#include<algorithm>
int n;
int num=1;
using namespace std;
struct acm{int b,e;
}a[100000];
bool cmp(acm a,acm b)
{return a.e<b.e;
}
int main()
{cin>>n;for(int i=0;i<n;i++){cin>>a[i].b>>a[i].e;}sort(a,a+n,cmp);int j=0;for(int i=1;i<n;i++){if(a[j].e<=a[i].b){num++;j=i;}}cout<<num<<endl;
}