NZIC 2026 Round 1（新西兰信息学竞赛 2024 第一轮）

D.Supply Scheduling（物资配送安排）

输入： 标准输入（stdin） 输出： 标准输出（stdout） 内存限制： 128 MB 时间限制： 2.0 秒

• problem statement
• submit
• submissions

---

题目描述

新西兰的街道上即将开设两家新的动物园：

• Aardvark Asylum
• Basilisk Biosphere

当动物园订购动物饲料时，需要支付两部分费用：

• 饲料本身的费用；
• 配送费用。

其中，配送费用是固定的，无论一次订购多少动物饲料，配送费用都一样。

并且：

所有配送都会在下单当天送达。

两家动物园意识到：

如果它们在同一天订购饲料，那么两家动物园合起来只需要支付一次配送费用。

这样就可以节省费用。

---

不幸的是，两家动物园都有各自固定的饲料配送时间表。

它们都恰好需要在：

$$N$$

天订购饲料。

Aardvark Asylum 的时间表记为：

$$A$$

其中包含 (N) 个整数。

(A) 中的每一个整数表示：

动物园开业之后经过多少天，需要进行一次饲料配送。

Basilisk Biosphere 的时间表记为：

$$B$$

同样包含 (N) 个整数。

(B) 中的每一个整数表示：

动物园开业之后经过多少天，需要进行一次饲料配送。

---

更正式地说：

对于所有满足：

$$0\le i\le N-1$$

的 (i)，Aardvark Asylum 会在开业后的：

$$A_i$$

天需要一次饲料配送。

Basilisk Biosphere 会在开业后的：

$$B_i$$

天需要一次饲料配送。

---

两家动物园都不能修改自己的配送时间表。

但是：

它们可以改变各自具体在哪一天开业。

你被聘请为顾问，需要帮助它们计算：

如果合理错开两家动物园的开业日期，使两家的配送日期尽可能重合，那么最少一共需要在多少个不同的日期订购饲料？

---

输入格式

第一行包含一个整数：

N

第二行包含 (N) 个用空格分隔的整数：

$$A_0,A_1,\dots,A_{N-1}$$

其中第 (i) 个整数表示：

Aardvark Asylum 在开业后的 (A_i) 天需要订购饲料。

保证这些整数按照严格递增顺序给出。

第三行包含 (N) 个用空格分隔的整数：

$$B_0,B_1,\dots,B_{N-1}$$

其中第 (i) 个整数表示：

Basilisk Biosphere 在开业后的 (B_i) 天需要订购饲料。

同样保证这些整数按照严格递增顺序给出。

---

输出格式

输出一个整数：

如果最优地错开两家动物园的开业日期，两家动物园总共最少需要在多少个不同的日期订购饲料。

---

数据范围

$$1\le N\le1000$$

对于所有：

$$0\le i\le N-1$$

都有：

$$1\le A_i,B_i\le10^9$$

并且对于所有：

$$1\le i\le N-1$$

都有：

$$A_i>A_{i-1}$$

以及：

$$B_i>B_{i-1}$$

也就是说，两个时间表中的日期都严格递增。

---

子任务

• 子任务 1（+20%）：

$$N=2$$

• 子任务 2（+25%）：

对于所有：

$$0\le i\le N-1$$

都有：

$$A_i\le2000$$

以及：

$$B_i\le2000$$

• 子任务 3（+30%）：

$$N\le100$$

• 子任务 4（+25%）：

没有额外限制。

---

样例说明

如果让 Basilisk Biosphere 比 Aardvark Asylum 提前 1 天开业，那么：

• Basilisk Biosphere 的第 2 次配送；
• 第 4 次配送；
• 第 5 次配送；

将分别与 Aardvark Asylum 的：

• 第 1 次配送；
• 第 4 次配送；
• 第 5 次配送；

发生在同一天。

因此，两家动物园原本一共有：

$$N+N=10$$

次配送需求。

其中有：

$$3$$

对配送可以合并到同一天。

所以只需要：

$$10-3=7$$

个不同的配送日期。

---

注意

如果你使用 Python，提交时请选择：

Python 3.6 (PyPy 7.3)

否则，即使算法已经达到最优效率，也可能因为运行速度问题无法通过部分子任务。

---

样例输入 1

5
2 3 6 8 10
1 3 8 9 11

样例输出 1

7

测试点编号	层级	N	特殊性质	标准输出	覆盖点与设计目的
1	弱数据	1	两数相等	1	最小规模，检查单个差值及统计初始化
2		4	两数组均为等差数列	4	多组相同差值，检查排序与连续计数
3	正常数据	3	两数组内部全部重复	-3	最大频次达到 N²，验证程序可能输出负数的实际行为
4		5	负数、零、正数及重复值混合	5	检查混合符号、重复元素产生的多重差值
5	极限值数据	10	数值接近 ±4×10¹⁸	10	检查 long long 大数减法及大差值排序，所有运算均未溢出