2021年（复赛S）CCF非专业级别软件能力认证全国卷真题（附详细答案解析）

2021 CCF 非专业级软件能力认证 CSP-J/S 2021 第二轮认证 提高组 时间：2021 年 10 月 23 日 14:30 ∼ 18:30 题目名称 廊桥分配 括号序列 回文 交通规划 题目类型 传统型 传统型 传统型 传统型 目录 airport bracket palin traffic 可执行文件名 airport bracket palin traffic 输入文件名 airport.in bracket.in palin.in traffic.in 输出文件名 airport.out bracket.out palin.out traffic.out 每个测试点时限 1.0 秒 1.0 秒 1.0 秒 3.0 秒 内存限制 512 MiB 512 MiB 512 MiB 512 MiB 子任务数目 20 20 25 20 测试点是否等分 是 是 是 是 提交源程序文件名 对于 C++ 语言 airport.cpp bracket.cpp palin.cpp traffic.cpp 对于 C 语言 airport.c bracket.c palin.c traffic.c 对于 Pascal 语言 airport.pas bracket.pas palin.pas traffic.pas 编译选项 对于 C++ 语言 ‐O2 ‐lm 对于 C 语言 ‐O2 ‐lm 对于 Pascal 语言 ‐O2 .注 .意 .事 .项（ .请 .仔 .细 .阅 .读） 1. 文件名（程序名和输入输出文件名）必须使用英文小写。 2. C/C++ 中函数 main() 的返回值类型必须是 int，程序正常结束时的返回值必须 是 0。 3. 提交的程序代码文件的放置位置请参考各省的具体要求。 4. 因违反以上三点而出现的错误或问题，申述时一律不予受理。 5. 若无特殊说明，结果的比较方式为全文比较（过滤行末空格及文末回车）。 6. 程序可使用的栈空间内存限制与题目的内存限制一致。 7. 全国统一评测时采用的机器配置为：Inter(R) Core(TM) i7-8700K CPU @3.70GHz， 内存 32GB。上述时限以此配置为准。 2021 CCF 非专业级软件能力认证 CSP-J/S 2021 第二轮认证 8. 只提供 Linux 格式附加样例文件。 9. 评测在当前最新公布的 NOI Linux 下进行，各语言的编译器版本以此为准。 第 2 页 共 13 页 2021 CCF 非专业级软件能力认证 CSP-J/S 2021 第二轮认证 廊桥分配（airport） 廊桥分配（airport） 【题目描述】 当一架飞机抵达机场时，可以停靠在航站楼旁的廊桥，也可以停靠在位于机场边缘 的远机位。乘客一般更期待停靠在廊桥，因为这样省去了坐摆渡车前往航站楼的周折。 然而，因为廊桥的数量有限，所以这样的愿望不总是能实现。 机场分为国内区和国际区，国内航班飞机只能停靠在国内区，国际航班飞机只能停 靠在国际区。一部分廊桥属于国内区，其余的廊桥属于国际区。 L市新建了一座机场，一共有 n个廊桥。该机场决定，廊桥的使用遵循“先到先得” 的原则，即每架飞机抵达后，如果相应的区（国内/国际）还有空闲的廊桥，就停靠在廊 桥，否则停靠在远机位（假设远机位的数量充足）。该机场只有一条跑道，因此不存在 两架飞机同时抵达的情况。 现给定未来一段时间飞机的抵达、离开时刻，请你负责将 n 个廊桥分配给国内区和 国际区，使停靠廊桥的飞机数量最多。 【输入格式】 从文件 airport.in 中读入数据。 输入的第一行包含 3 个正整数 n,m1,m2 分别表示廊桥的个数、国内航班飞机的数 量、国际航班飞机的数量。 接下来 m1 行是国内航班的信息，第 i 行包含 2 个正整数 a1,i, b1,i，分别表示一架国 内航班飞机的抵达、离开时刻。 接下来 m2 行是国际航班的信息，第 i 行包含 2 个正整数 a2,i, b2,i，分别表示一架国 际航班飞机的抵达、离开时刻。 每行的多个整数由空格分隔。 【输出格式】 输出到文件 airport.out 中。 输出一个正整数，表示能够停靠廊桥的飞机数量的最大值。 【样例 1 输入】 1 3 5 4 2 1 5 3 3 8 4 6 10 5 9 14 第 3 页 共 13 页 2021 CCF 非专业级软件能力认证 CSP-J/S 2021 第二轮认证 廊桥分配（airport） 6 13 18 7 2 11 8 4 15 9 7 17 10 12 16 【样例 1 输出】 1 7 【样例 1 解释】 图 1: 样例图片 在图中，我们用抵达、离开时刻的数对来代表一架飞机，如 (1, 5) 表示时刻 1 抵