小欧的选数乘积

OPPO 笔试真题 · 2023 秋招 · 算法岗

判题请到牛客原题提交。

题目描述

小欧拿到了两个正整数$x$和$y$，她想进行一些操作使得$x$不小于$y$，操作方式是：选择$a$数组中的一个元素$a_i$，将$x$乘以$a_i$，并删掉$a$数组中所有的$a_i$。

小欧想知道，自己最少进行多少次操作，可以使得$x$不小于$y$？

输入格式

第一行输入两个正整数$x$和$y$，用空格隔开。

第二行输入一个正整数$n$，代表数组大小。

第三行输入$n$个正整数$a_i$，代表数组的元素。

$1\leq x,y,a_i \leq 10^{9}$

$1\leq n \leq 10^5$

输出格式

如果小欧无法在有限的操作下使得$x$不小于$y$，则输出-1。

否则输出一个整数，代表小欧的操作次数。

示例

示例 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

说明：

小欧不需要任何操作。

---

解题思路

第一步：理解问题本质

操作有两步：把 $x$ 乘上 $a_i$，再删掉数组里所有等于 $a_i$ 的元素。

第二半步是关键：一旦选了值 $v$，数组里所有 $v$ 都会消失，之后再也选不到 $v$。
所以每种不同的值最多只能用一次。数组里重复的元素除了「表示 $v$ 存在」之外毫无作用。

问题于是变成：从不同的值里挑若干个数乘到 $x$ 上，最少挑几个能让 $x \ge y$。

第二步：贪心 —— 每次挑最大的

固定操作次数 $k$，要让乘积最大，显然应该挑最大的 $k$ 个不同值：把其中任何一个换成更小的值，
乘积只会变小。因此「答案为 $k$」等价于「最大的 $k$ 个不同值乘起来 $\ge y$」。

这直接给出了做法：把不同值从大到小排序，依次乘上去，第一次满足 $x \ge y$ 时的操作次数就是答案。
因为乘积是单调不减的（$a_i \ge 1$），「第一次满足」就是最少次数。

第三步：什么时候无解，以及怎么防止数字爆炸

两种无解情况，本质都是「能乘的数不够多或不够大」：

1. 不同值里最大的那个是 1 —— 乘 1 不改变 $x$，永远达不到；
2. 所有不同值都乘完了仍然 $x < y$ —— 比如 $x=1, y=8$ 而数组只有一个不同的值 2。

因为 $a_i$ 可以到 $10^9$、$n$ 可以到 $10^5$，一路死乘下去会得到天文数字（位数能到几十万位），
比较运算都会变慢。所以一旦 $x \ge y$ 就立刻返回：这样 $x$ 始终小于 $y \le 10^9$，
乘一个 $a_i$ 最多到 $10^{18}$，完全不用担心溢出。

---

完整代码实现

import sys


def solve() -> None:
    """不同值降序去重后依次相乘，乘到不小于 y 为止"""
    data = sys.stdin.buffer.read().split()
    if not data:
        return
    x = int(data[0])
    y = int(data[1])
    n = int(data[2])

    if x >= y:
        sys.stdout.write("0\n")
        return

    # 同一个值只能选一次，先把重复的合并掉，再从大到小用
    values = sorted({int(v) for v in data[3:3 + n]}, reverse=True)

    ops = 0
    for v in values:
        if v == 1:
            # 后面全是 1 了，乘上去没有任何效果
            break
        x *= v
        ops += 1
        if x >= y:
            sys.stdout.write(str(ops) + "\n")
            return

    sys.stdout.write("-1\n")


if __name__ == "__main__":
    solve()

---

示例推演

示例 1：x = 3, y = 40, a = [2, 3, 4, 4]

不同值为 $\{2, 3, 4\}$，从大到小排好：$4, 3, 2$。

第几次	选的值	$x$ 变化	是否满足 $x \ge 40$
1	4	3 → 12	否
2	3	12 → 36	否
3	2	36 → 72	是

三次操作后 $x = 72 \ge 40$，答案是 3。

（题面示例是先选 3 再选 4，顺序不同但次数一样；固定次数的乘积与先后顺序无关，
所以从大到小乘只是让「达到目标」来得更快。）

示例 2：x = 2, y = 5, a = [2, 2, 2, 2, 2]

不同值只有 $\{2\}$。第一次操作后 $x = 4$，同时所有 2 都被删掉，数组空了，
$4 < 5$ 且无法继续，输出 -1。

示例 3：x = 5, y = 5, a = [2, 2, 2, 2, 2]

一开始就满足 $x \ge y$，不需要任何操作，输出 0。

补充例子：x = 6, y = 100, a = [2, 3, 5]

第几次	选的值	$x$ 变化	是否满足
1	5	6 → 30	否
2	3	30 → 90	否
3	2	90 → 180	是

答案 3。注意即使数组还有元素，也要用「最大的几个」去乘才最快。

---

复杂度分析

解法	时间复杂度	空间复杂度	说明
枚举所有子集	O(2ⁿ)	O(n)	只有理论意义
去重 + 降序排序 + 贪心	O(n log n)	O(n)	推荐，主要开销在排序
值域很小时用桶排序	O(n + max a)	O(max a)	一般不需要

---

易错点总结

1. 把同一个值用多次

a = [2,2,2] 时有人会算成「乘三次 2」，但选一次 2 就把三个 2 全删了，
真正的效果只是乘一次。代码里用 set 去重正是为了避免这个问题。

2. 忘记「一开始就够」的情况

$x \ge y$ 时答案是 0，必须在循环前特判，否则会输出 1。

3. 只用「最大值是不是 1」判断无解

最大值大于 1 也可能无解。例如 $x = 1, y = 100$，数组为 $[2,3]$：
$1 \times 3 \times 2 = 6 < 100$，仍然输出 -1。必须老老实实乘完所有不同值。

4. 一路死乘不剪枝

$10^9$ 连乘 $10^5$ 次会得到一个几十万位的整数，虽然 Python 不会溢出，
但乘法和比较都会明显变慢。正确做法是一旦 $x \ge y$ 就立刻返回。

5. 排序方向写反

要最快达到目标，必须从大到小乘。从小到大乘虽然最终乘积一样（乘法可交换），
但「第一次满足」的位置会靠后，答案就错了。

6. 读入的个数

第三行有 n 个数，用 data[3:3+n] 取，避免把第一行的两个数算进数组。

---

扩展思考

• 如果每次只删掉选中的那一个元素（而不是所有相同值）：不同值可以重复使用，
  答案就变成「取最大的若干个（允许重复）」，可以直接排序取前缀。
• 如果 $a_i$ 可以是 0 或负数：乘 0 会让 $x$ 永远停在 0，负数还会让符号翻转，
  贪心就不再成立，需要按正负分开讨论。
• 如果要求恰好 $k$ 次操作（不能提前停）：那就变成「最大乘积」问题，要挑绝对值最大的 $k$ 个并处理符号。
• 本题也说明了「去重」在贪心题里的重要性：重复元素既不能多用，也不影响答案。

---

相关题目

• 小欧的等差数列