103762: [Atcoder]ABC376 C - Prepare Another Box
Description
Score : $350$ points
Problem Statement
There are $N$ toys numbered from $1$ to $N$, and $N-1$ boxes numbered from $1$ to $N-1$. Toy $i\ (1 \leq i \leq N)$ has a size of $A_i$, and box $i\ (1 \leq i \leq N-1)$ has a size of $B_i$.
Takahashi wants to store all the toys in separate boxes, and he has decided to perform the following steps in order:
- Choose an arbitrary positive integer $x$ and purchase one box of size $x$.
- Place each of the $N$ toys into one of the $N$ boxes (the $N-1$ existing boxes plus the newly purchased box). Here, each toy can only be placed in a box whose size is not less than the toy's size, and no box can contain two or more toys.
He wants to execute step $2$ by purchasing a sufficiently large box in step $1$, but larger boxes are more expensive, so he wants to purchase the smallest possible box.
Determine whether there exists a value of $x$ such that he can execute step $2$, and if it exists, find the minimum such $x$.
Constraints
- $2 \leq N \leq 2 \times 10^5$
- $1 \leq A_i, B_i \leq 10^9$
- All input values are integers.
Input
The input is given from Standard Input in the following format:
$N$
$A_1$ $A_2$ $\dots$ $A_N$
$B_1$ $B_2$ $\dots$ $B_{N-1}$
Output
If there exists a value of $x$ such that Takahashi can execute step $2$, print the minimum such $x$. Otherwise, print -1.
Sample Input 1
4 5 2 3 7 6 2 8
Sample Output 1
3
Consider the case where $x=3$ (that is, he purchases a box of size $3$ in step $1$).
If the newly purchased box is called box $4$, toys $1,\dots,4$ have sizes of $5$, $2$, $3$, and $7$, respectively, and boxes $1,\dots,4$ have sizes of $6$, $2$, $8$, and $3$, respectively. Thus, toy $1$ can be placed in box $1$, toy $2$ in box $2$, toy $3$ in box $4$, and toy $4$ in box $3$.
On the other hand, if $x \leq 2$, it is impossible to place all $N$ toys into separate boxes. Therefore, the answer is $3$.
Sample Input 2
4 3 7 2 5 8 1 6
Sample Output 2
-1
No matter what size of box is purchased in step $1$, no toy can be placed in box $2$, so it is impossible to execute step $2$.
Sample Input 3
8 2 28 17 39 57 56 37 32 34 27 73 28 76 61 27
Sample Output 3
37
Output
得分：$350$ 分
问题陈述
有 $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$。
高桥想要将所有玩具分别存放在不同的盒子里，他已经决定按以下步骤进行：
- 选择一个任意的正整数 $x$ 并购买一个大小为 $x$ 的盒子。
- 将每个玩具放入 $N$ 个盒子中的一个（$N-1$ 个现有盒子加上新购买的盒子）。 这里，每个玩具只能放入大小不小于玩具大小的盒子中，且没有盒子可以包含两个或更多玩具。
他希望通过在第一步购买足够大的盒子来执行第二步，但是更大的盒子更贵，所以他希望购买尽可能小的盒子。
确定是否存在一个 $x$ 的值，使得他可以执行第二步，如果存在，找出这样的最小 $x$。
约束条件
- $2 \leq N \leq 2 \times 10^5$
- $1 \leq A_i, B_i \leq 10^9$
- 所有输入值都是整数。
输入
输入从标准输入以下格式给出：
$N$
$A_1$ $A_2$ $\dots$ $A_N$
$B_1$ $B_2$ $\dots$ $B_{N-1}$
输出
如果存在一个 $x$ 的值，使得高桥可以执行第二步，打印这样的最小 $x$。否则，打印 -1。
示例输入 1
4 5 2 3 7 6 2 8
示例输出 1
3
考虑 $x=3$ 的情况（即他在第一步购买了一个大小为 $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$。
示例输入 2
4 3 7 2 5 8 1 6
示例输出 2
-1
无论在第一步购买什么大小的盒子，都没有玩具可以放在盒子 $2$ 中，所以无法执行第二步。
示例输入 3
8 2 28 17 39 57 56 37 32 34 27 73 28 76 61 27
示例输出 3
37