考点：贪心

数据规模 n ≤ 1e5 ｜ 限制 1 秒 / 256MB ｜ 标准输入输出

题目画像

• 数据规模：n ≤ 1e5
• 元素值域：x ≤ 1e9，y ≤ 1e9，a_i ≤ 1e9（注意整数类型选择，避免溢出）
• 复杂度门槛：只允许 O(n log n) 及更优，朴素 O(n²) 会超时。
• 源站时限：1 秒（牛客口径，非本题专属门槛）

解题思路

推荐方向：贪心

本题切入点

每次操作会删掉所有等于所选值 a_i 的元素，因此按值从大到小排序，每次取当前最大的值乘上去，直到 x ≥ y。

每一步都取当前最优，靠问题性质保证局部最优能拼成全局最优。

思路框架（贪心 通法 · 非本题专属）

1. 找出「局部最优怎么选」（往往与排序后的顺序有关）。
2. 论证（或理性相信）这个贪心策略不会被反例击破：常用交换论证法。
3. 按策略一次扫描（通常要先排序）得到答案。
4. 若贪心无法证明，考虑改用 DP（贪心的反例通常来自「当前最优影响后续选择」）。

实现要点：贪心题关键在于排序规则：按什么关键字排序决定了策略是否正确。

复杂度：时间 O(n log n)（含排序） ｜ 空间 O(1) ~ O(n)

该范式的通法易错点

• 策略不成立却当成贪心做（典型错因）。
• 排序关键字选错，或相同关键字时的次级规则没考虑。

对照本题

• 数据规模 n ≤ 1e5，只允许 O(n log n) 及更优，朴素 O(n²) 会超时。
• 元素值域最大到 1e9 —— 求和 / 相乘时记得开 64 位整数。

样例解读

样例 1：输入 3 40 / 4 / 2 3 4 4 → 输出 3

第一次操作，小欧选择数字3， x 变成9，此时数组为[2,4,4]

第二次操作，小欧选择数字4， x 变成36，此时数组为[2]

第三次操作，小欧选择数字2， x 变成72，此时数组为空。三次操作后 x 不小于 y

操作的方式不是唯一的，但可以证明操作的最小次数为3。

样例 2：输入 2 5 / 5 / 2 2 2 2 2 → 输出 -1

当小欧选择2后， x 变成4，但此时数组为空。因此无法继续操作， x 永远不可能不小于 y 。

样例 3：输入 5 5 / 5 / 2 2 2 2 2 → 输出 0

小欧不需要任何操作。