AT_abc348_c [ABC348C] Colorful Beans

题目描述

有 $N$ 种豆子，每种豆子各有 $1$ 粒。第 $i$ 种豆子的美味度为 $A_i$，颜色为 $C_i$。这些豆子被混合在一起，只能通过颜色来区分。

你可以选择一种颜色，并从该颜色的豆子中任选一粒吃掉。请通过巧妙地选择颜色，使得你可能吃到的豆子的美味度的最小值最大。输出该最大值。

输入格式

输入以如下格式从标准输入读入。

$N$
$A_1$ $C_1$
$A_2$ $C_2$
$\vdots$
$A_N$ $C_N$

输出格式

输出你可能吃到的豆子的美味度的最小值的最大值，作为一个整数。

输入输出样例 #1

输入 #1

4
100 1
20 5
30 5
40 1

输出 #1

40

输入输出样例 #2

输入 #2

10
68 3
17 2
99 2
92 4
82 4
10 3
100 2
78 1
3 1
35 4

输出 #2

35

说明/提示

限制条件

• $1 \leq N \leq 2 \times 10^{5}$
• $1 \leq A_i \leq 10^{9}$
• $1 \leq C_i \leq 10^{9}$
• 输入均为整数。

样例解释 1

请注意，同一种颜色的豆子无法互相区分。可以选择的颜色有颜色 $1$ 和颜色 $5$。

• 颜色 $1$ 的豆子有 $2$ 粒，美味度分别为 $100,\ 40$。因此，选择颜色 $1$ 时可能吃到的美味度的最小值为 $40$。
• 颜色 $5$ 的豆子有 $2$ 粒，美味度分别为 $20,\ 30$。因此，选择颜色 $5$ 时可能吃到的美味度的最小值为 $20$。

为了最大化美味度的最小值，应选择颜色 $1$，此时的最小值为 $40$，输出 $40$。

由 ChatGPT 4.1 翻译