Skip to content

洛谷 - P7913 廊桥分配

检测到 KaTeX 加载失败,可能会导致文中的数学公式无法正常渲染。

题面

题目描述

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

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

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

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

输入格式

输入的第一行,包含三个正整数 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},分别表示一架国际航班飞机的抵达、离开时刻。

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

输出格式

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

输入输出样例

样例输入 #1

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

样例输出 #1

7

样例解释 #1

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

我们以表格中阴影部分的计算方式为例,说明该表的含义。在这一部分中,国际区有 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

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

样例输出 #2

4

样例解释 #2

当国内区分配 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 架飞机先后使用。

数据范围与约定

对于 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,m1]i \in [1, m_1],都有 a1,i<b1,ia_{1, i} < b_{1, i},以及对于每个 i[1,m2]i \in [1, m_2],都有 a2,i<b2,ia_{2, i} < b_{2, i}

思路

将每个航班存储为一个 pair<int, int> ,第一关键字表示该航班的抵达时间,第二关键字表示该航班的离开时间。

f(x),g(x)f(x), g(x) 分别表示有 xx 个廊桥分配给国内(国际)航班时停靠廊桥的飞机数量的最大值,则最后答案可以转化成 max(f(x)+g(nx)), (0xn)\max(f(x) + g(n - x)),\ (0 \leq x \leq n)

将廊桥一条一条的分配给国内航班,并使用 set 维护当前未在廊桥上的飞机。

当一条廊桥加入后,从 set 中删去以下飞机:

  1. set 中最早抵达的飞机 p0p_0 ,并将当前的 cnt+1cnt + 1
  2. p0p_0 离开后最早抵达的飞机 p1p_1 ,并将当前的 cnt+1cnt + 1
  3. p1p_1 离开后最早抵达的飞机 p2p_2 ,并将当前的 cnt+1cnt + 1

以此类推,直到没有飞机可以操作为止。该操作可以使用 lower_bound 查找来降低时间复杂度。完成后将新增的可以停靠廊桥的飞机加入答案数组中。

国际航班同理,按照上述步骤操作即可。

时间复杂度 O(mlogm)O(m \log m)

代码

#include <bits/stdc++.h>

using namespace std;

int n, m[2], a, b, cnt[2][100005], ans;
set<pair<int, int>> s;

int main() {
    cin >> n >> m[0] >> m[1];
    for (int k = 0; k < 2; k++) {
        for (int i = 1; i <= m[k]; i++) {
            cin >> a >> b;
            s.insert(make_pair(a, b));
        }
        for (int i = 1; i <= n; i++) {
            int p = 0, c = 0;
            while (true) {
                auto it = s.lower_bound(make_pair(p, 0));
                if (it == s.end()) break;
                p = it->second;
                s.erase(it);
                c++;
            }
            cnt[k][i] = cnt[k][i - 1] + c;
        }
        s.clear();
    }
    for (int i = 0; i <= n; i++) {
        ans = max(ans, cnt[0][i] + cnt[1][n - i]);
    }
    cout << ans << endl;
    return 0;
}