luogu#P9925. [POI 2023/2024 R1] Zapobiegliwy student
[POI 2023/2024 R1] Zapobiegliwy student
题目背景
译自 XXXI Olimpiada Informatyczna - I etap Zapobiegliwy student。
题目描述
考虑如下的一个简单问题:
你有 个线段在数轴上,你要选出尽量多的线段,使它们两两不交。
我知道你一定会做,但你需要解决这个:
你有 个线段在数轴上,你要选出尽量多的线段对 ,即最大化 。
满足 个要求:
- 两两不交。
- 两两不交。
- 两两不交。
- 两两不交。
其中 , 与 不能相同。
输入格式
第一行一个正整数 。
接下来 行每行两个正整数 ,表示一个线段的两个端点。
两个线段 不交当且仅当 或 。
输出格式
第一行一个正整数 。
接下来 行,每行两个正整数 ,表示一对线段的编号。
8
1 5
3 10
4 8
9 12
11 16
14 15
20 22
15 21
3
1 3
4 6
8 7
见附件
见附件
见附件
见附件
提示
如果你的第一行正确但是方案不对(可以不输出方案,此时不要有换行),你能得到 的分数。
如果你的方案合法并且第一行和答案相差不超过 ,你能得到 的分数。
子任务编号 | 限制 | 分值 |
---|---|---|
1 | 40 | |
2 | 60 |