华师一附中OI组

标题: P1803 凌乱的yyy / 线段覆盖 [打印本页]
作者: 倚窗倾听风吹雨    时间: 2018-9-8 16:08
标题: P1803 凌乱的yyy / 线段覆盖
https://www.luogu.org/problemnew/show/P1803


题目背景
快noip了，yyy很紧张！

题目描述
现在各大oj上有n个比赛，每个比赛的开始、结束的时间点是知道的。

yyy认为，参加越多的比赛，noip就能考的越好（假的）

所以，他想知道他最多能参加几个比赛。

由于yyy是蒟蒻，如果要参加一个比赛必须善始善终，而且不能同时参加2个及以上的比赛。

输入输出格式
输入格式：
第一行是一个整数n ，接下来n行每行是2个整数ai,bi(ai<bi)，表示比赛开始、结束的时间。

输出格式：
一个整数最多参加的比赛数目。

输入输出样例
输入样例#1：
3
0 2
2 4
1 3
输出样例#1：
2
说明
对于20%的数据，n≤10；
对于50%的数据，n≤1000；
对于70%的数据，n≤100000；
对于100%的数据，n≤1000000，0≤ai＜bi≤1000000。
作者: 黄煦喆    时间: 2018-9-9 20:54
  1. #include<iostream>
  2. #include<algorithm>
  3. using namespace std;
  4. int n,ans=1,l=1,r=2;
  5. struct times
  6. {
  7.     int a,b;
  8. }t[1000001];
  9. bool operator < (times x,times y)
  10. {
  11.     return x.b<y.b;
  12. }
  13. int main()
  14. {
  15.     cin>>n;
  16.     for(int i=1;i<=n;i++)cin>>t[i].a>>t[i].b;
  17.     sort(t+1,t+n+1);
  18.     while(r<=n)
  19.     {
  20.         if(t[r].a>=t[l].b)ans++,l=r;
  21.         r++;
  22.     }
  23.     cout<<ans;
  24.     return 0;
  25. }
复制代码




欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2