P1803 凌乱的yyy / 线段覆盖
题目背景
Python 用户可以尝试使用 pypy3 提交试题。
快 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≤103；
- 对于 70% 的数据，n≤105；
- 对于 100% 的数据，1≤n≤106，0≤ai<bi≤106。
题目解析
通过分析题目得知我们需要知道最多可以参加多少个比赛（即，通过调整参加的顺序使得参加的个数最多）
怎么样才能最多呢——>一场比赛花费的时间最少的时候——>相同时间起点的情况下一场比赛的结束时间在时间轴上越靠右，这样就能有更多的时间机会去参加其他比赛。
思路：利用结构体数组存储时间，输入时间后我们利用结束时间的大小进行排序，然后逐个进行选择，选择之后利用bool类型的check数组存储选取情况，可以选就选。
代码
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1000005;bool check[maxn];
struct px{int l;int r;
}arr[maxn];bool cmp(px x, px y)
{return x.r < y.r;
}
int main()
{int n;cin >> n;for(int i = 0; i < n; i++){cin >> arr[i].l >> arr[i].r;}sort(arr, arr + n, cmp);//for(int i = 0; i < n; i++)cout << arr[i].r << " ";//进行选择int ans = 0, f, a, b;for(int i = 0; i < n; i++){f = 0;a = arr[i].l, b = arr[i].r;for(int j = a; j <= b; j++){if(check[j]){//检查选取状态f = 1;break;}}if(f == 0){ans++;//标记选取状态check[a] = true;check[b - 1] = true;}}cout << ans;return 0;
}