分数: 400 点
问题陈述
给你正整数 a 和 b 这样 a\leq b,以及正整数序列 A = (A_1, A_2, \ldots, A_N).
在此序列中,您可以执行以下操作任意次数(可能为零):
- 选择不同的索引 i, j (1\leq i, j \leq N)。添加 a to A_i 并减去 b 来自 A_j.
找到最大可能值 \min(A_1, A_2, \ldots, A_N) 操作后。
约束
- 2\leq N\leq 3\times 10^5
- 1\leq a\leq b\leq 10^9
- 1\leq A_i\leq 10^{9}
输入
输入由标准输入按以下格式给出:
N a b A_1 A_2 \ldots A_N
输出
打印最大可能值 \min(A_1, A_2, \ldots, A_N) 操作后。
示例输入 1
3 2 2 1 5 9
示例输出 1
5
这是实现的一种方法 \min(A_1, A_2, A_3) = 5.
- 执行操作 i = 1, j = 3. A 变为 (3, 5, 7).
- 执行操作 i = 1, j = 3. A 变为 (5, 5, 5).
示例输入 2
3 2 3 11 1 2
示例输出 2
3
这是实现的一种方法 \min(A_1, A_2, A_3) = 3.
- 执行操作 i = 1, j = 3. A 变为 (13, 1, -1).
- 执行操作 i = 2, j = 1. A 变为 (10, 3, -1).
- 执行操作 i = 3, j = 1. A 变为 (7, 3, 1).
- 执行操作 i = 3, j = 1. A 变为 (4, 3, 3).
示例输入 3
3 1 100 8 5 6
示例输出 3
5
你可以实现 \min(A_1, A_2, A_3) = 5 根本不执行该操作。
示例输入 4
6 123 321 10 100 1000 10000 100000 1000000
示例输出 4
90688