#1195. 「CSP-S 2021」廊桥分配

    ID: 1195 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>贪心数据结构文件 IOsetcsp-s2021

「CSP-S 2021」廊桥分配

题目描述

当一架飞机抵达机场时,可以停靠在航站楼旁的廊桥,也可以停靠在位于机场边缘的远机位。乘客一般更期待停靠在廊桥,因为这样省去了坐摆渡车前往航站楼的周折。然而,因为廊桥的数量有限,所以这样的愿望不总是能实现。

机场分为国内区和国际区,国内航班飞机只能停靠在国内区,国际航班飞机只能停靠在国际区。一部分廊桥属于国内区,其余的廊桥属于国际区。

L 市新建了一座机场,一共有 nn 个廊桥。该机场决定,廊桥的使用遵循“先到先得”的原则,即每架飞机抵达后,如果相应的区(国内/国际)还有空闲的廊桥,就停靠在廊桥,否则停靠在远机位(假设远机位的数量充足)。该机场只有一条跑道,因此不存在两架飞机同时抵达的情况。

现给定未来一段时间飞机的抵达、离开时刻,请你负责将 nn 个廊桥分配给国内区和国际区,使停靠廊桥的飞机数量最多。

输入格式

从文件 airport.in 中读入数据。

输入的第一行,包含三个正整数 n,m1,m2n, m_1, m_2,分别表示廊桥的个数、国内航班飞机的数量、国际航班飞机的数量。

接下来 m1m_1 行,是国内航班的信息,第 ii 行包含两个正整数 a1,i,b1,ia_{1, i}, b_{1, i},分别表示一架国内航班飞机的抵达、离开时刻。

接下来 m2m_2 行,是国际航班的信息,第 ii 行包含两个正整数 a2,i,b2,ia_{2, i}, b_{2, i},分别表示一架国际航班飞机的抵达、离开时刻。

每行的多个整数由空格分隔。

输出格式

输出到文件 airport.out 中。

输出一个正整数,表示能够停靠廊桥的飞机数量的最大值。

样例 1

3 5 4
1 5
3 8
6 10
9 14
13 18
2 11
4 15
7 17
12 16

7

05jaghri.png

在图中,我们用抵达、离开时刻的数对来代表一架飞机,如 (1,5)(1, 5) 表示时刻 11 抵达、时刻 55 离开的飞机;用 ×\times 表示该飞机停靠在廊桥,用 \surd 表示该飞机停靠在远机位。

我们以表格中阴影部分的计算方式为例,说明该表的含义。在这一部分中,国际区有 22 个廊桥,44 架国际航班飞机依如下次序抵达:

  1. 首先 (2,11)(2, 11) 在时刻 22 抵达,停靠在廊桥。
  2. 然后 (4,15)(4, 15) 在时刻 44 抵达,停靠在另一个廊桥。
  3. 接着 (7,17)(7, 17) 在时刻 77 抵达,这时前 22 架飞机都还没离开、都还占用着廊桥,而国际区只有 22 个廊桥,所以只能停靠远机位。
  4. 最后 (12,16)(12, 16) 在时刻 1212 抵达,这时 (2,11)(2, 11) 这架飞机已经离开,所以有 11 个空闲的廊桥,该飞机可以停靠在廊桥。

根据表格中的计算结果,当国内区分配 22 个廊桥、国际区分配 11 个廊桥时,停靠廊桥的飞机数量最多,一共 77 架。

2 4 6
20 30
40 50
21 22
41 42
1 19
2 18
3 4
5 6
7 8
9 10

4

当国内区分配 22 个廊桥、国际区分配 00 个廊桥时,停靠廊桥的飞机数量最多,一共 44 架,即所有的国内航班飞机都能停靠在廊桥。

需要注意的是,本题中廊桥的使用遵循“先到先得”的原则,如果国际区只有 11 个廊桥,那么将被飞机 (1,19)(1, 19) 占用,而不会被 (3,4)(3, 4)(5,6)(5, 6)(7,8)(7, 8)(9,10)(9, 10)44 架飞机先后使用。

样例 3

见附加文件中的 [airport3.in](file:airport3.in) 与 [airport3.ans](file:airport3.ans)。

数据范围与提示

对于 20%20 \% 的数据,n100n \le 100m1+m2100m_1 + m_2 \le 100
对于 40%40 \% 的数据,n5000n \le 5000m1+m25000m_1 + m_2 \le 5000
对于 100%100 \% 的数据,1n1051 \le n \le {10}^5m1,m21m_1, m_2 \ge 1m1+m2105m_1 + m_2 \le {10}^5,所有 a1,i,b1,i,a2,i,b2,ia_{1, i}, b_{1, i}, a_{2, i}, b_{2, i} 为数值不超过 108{10}^8 的互不相同的正整数,且保证对于每个 i[1,n]i \in [1, n]a1,i<b1,ia_{1, i} < b_{1, i}a2,i<b2,ia_{2, i} < b_{2, i}