Colorful Beans

题目描述

有 $N$ 种豆子，每种豆子各一颗。第 $i$ 种豆子的美味度为 $A_i$，颜色为 $C_i$。这些豆子被混合在一起，只能通过颜色来区分。 你将选择一种颜色的豆子并吃一颗该颜色的豆子。通过选择最优的颜色，使你吃到的豆子的最小可能美味度最大化。

输入格式

输入从标准输入给出，格式如下： $N$ $A_1$ $C_1$ $A_2$ $C_2$ $\vdots$ $A_N$ $C_N$

输出格式

以整数形式输出你吃到的豆子的最小可能美味度的最大值。

4
100 1
20 5
30 5
40 1

40

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

35

提示

$1 \leq N \leq 2 \times 10^{5}$ $1 \leq A_i \leq 10^{9}$ $1 \leq C_i \leq 10^{9}$ 所有输入值均为整数。注意相同颜色的豆子彼此无法区分。 你可以选择颜色 $1$ 或 颜色 $5$。

颜色 $1$ 有两种豆子， 美味度分别为 $100$ 和 $40$。因此，选择颜色 $1$ 时的最小美味度为 $40$。 颜色 $5$ 有两种豆子， 美味度分别为 $20$ 和 $30$。因此，选择颜色 $5$ 时的最小美味度为 $20$。

为了使最小美味度最大化，应选择颜色 $1$，因此输出该情况下的最小美味度：$40$.

标签: AtCoder|abc348C

来源

AtCoder|abc348C