Prepare Another Box

题目描述

有 $N$$ 个玩具，编号为 $1$ 到 $N$，以及 $N-1$$ 个盒子，编号为 $1$ 到 $N-1$。 玩具 $i\ (1 \leq i \leq N)$ 的大小为 $A_i$，盒子 $i\ (1 \leq i \leq N-1)$ 的大小为 $B_i$。 Takahashi 想把所有玩具放在不同的盒子里，他决定按以下步骤操作：

选择任意的正整数 $x$ 并购买一个大小为 $x$ 的盒子。 将每个 $N$ 个玩具放入 $N$ 个盒子中的一个（原有的 $N-1$ 个盒子加上新购买的盒子）。 这里，每个玩具只能放入大小不小于该玩具大小的盒子，并且每个盒子最多只能放一个玩具。

他希望通过在步骤 1 中购买一个足够大的盒子来完成步骤 2，但更大的盒子更贵，因此他想购买尽可能小的盒子。 判定是否存在一个 $x$ 使得他可以执行步骤 2，如果存在，求最小的这样的 $x$。

输入格式

输入通过标准输入按以下格式给出： $N$ $A_1$ $A_2$ $\dots$ $A_N$ $B_1$ $B_2$ $\dots$ $B_{N-1}$

输出格式

如果存在一个 $x$ 使得 Takahashi 可以执行步骤 2，输出最小的这样的 $x$。否则，输出 $-1$。

4
5 2 3 7
6 2 8

3

4
3 7 2 5
8 1 6

-1

8
2 28 17 39 57 56 37 32
34 27 73 28 76 61 27

37

提示

$2 \leq N \leq 2 \times 10^5$ $1 \leq A_i, B_i \leq 10^9$ 所有输入值均为整数。考虑 $x=3$ 的情况（即他在步骤 1 中购买了一个大小为 $3$ 的盒子）。 若把新购买的盒子称为盒子 $4$，玩具 $1,\dots,4$ 的大小分别为 $5$、$2$、$3$ 和 $7$，盒子 $1,\dots,4$ 的大小分别为 $6$、$2$、$8$ 和 $3$。 因此，玩具 $1$ 可以放入盒子 $1$，玩具 $2$ 放入盒子 $2$，玩具 $3$ 放入盒子 $4$，玩具 $4$ 放入盒子 $3$。 另一方面，如果 $x \leq 2$，则不可能把所有 $N$ 个玩具放入不同的盒子。 因此，答案是 $3$。
无论在步骤 1 中购买多大的盒子，都没有玩具可以放入盒子 $2$，因此无法执行步骤 2。

标签: AtCoder|abc376C

来源

AtCoder|abc376C