最少操作次数计算

Question

用python写程序

给你两个数组 nums 和 target 。
在一次操作中，你可以将 nums 中的任意一个元素递增 1 。
返回要使 target 中的每个元素在 nums 中至少存在一个倍数所需的最少操作次数。

示例 1：
输入：nums = [1,2,3], target = [4]
输出：1
解释：满足题目条件的最少操作次数是 1 。
将 3 增加到 4 ，需要 1 次操作，4 是目标值 4 的倍数。

示例 2：
输入：nums = [8,4], target = [10,5]
输出：2
解释：满足题目条件的最少操作次数是 2 。
将 8 增加到 10 ，需要 2 次操作，10 是目标值 5 和 10 的倍数。

示例 3：
输入：nums = [7,9,10], target = [7]
输出：0
解释：
数组中已经包含目标值 7 的一个倍数，不需要执行任何额外操作。

示例 4：
输入：nums = [7,9,10], target = [427]
输出：417

提示：
1 <= nums.length <= 5 * 10^4
1 <= target.length <= 4
target.length <= nums.length
1 <= nums[i], target[i] <= 10^4

Answer 1

下面给出一种 Python 解法，思路是：

对于每个目标数 $t$ ，我们希望在数组 nums 中至少有一个数（经过若干次“+1”操作后）能变成 $t$ 的倍数。
由于一个数经过更新后得到的值 $v$ ，如果满足 $v \bmod t=0$ ，那么这个数可以“覆盖”目标 $t$ ；而一个数更新后的值可能同时满足多个 $t$ 的条件。
因为 target 数组长度最多 4，我们可以用一个 4 位的二进制掩码表示哪些目标已“被覆盖”。最终要求掩码为 $(1<<m)-1$ （全部 1）。
对于每个 nums 中的数 $x$ $x$ ，我们可以考虑“将其更新为一个恰好能覆盖某个子集 $S$ $S$ （ $S\subseteq$ $S \subseteq$ target）的倍数”的方案。
- 设 $L = \mathrm{lcm}(\{t: t\in S\})$ ，则将 $x$ 更新为不小于 $x$ 的最小 $L$ 的倍数： $v = \left\lceil \frac{x}{L} \right\rceil \times L,$ 操作次数为 $v-x$ 。
- 更新后的 $v$ 不仅必定是 $S$ 中所有目标的倍数，而且可能正好是 target 中更多目标的倍数；我们扫描 target 得到“实际覆盖”子集（记为一个二进制掩码）。
每个元素最多只能使用一次。令 dp[mask] 表示“经过若干个（若干个 nums 元素各选一种更新方案）的选择后，能使得覆盖状态达到 mask 所需的最少操作数”。初始 dp[0]=0，其它 dp[mask]=∞。
对于 nums 中的每个数，我们枚举它所有的候选更新方案，然后用 0/1 背包的思想更新 dp。最后答案即 dp[ FULL ] ，其中 $FULL = (1<<m)-1$ 。

下面是完整代码（注意：输入格式假设两行分别给出 nums 和 target，形如 [1,2,3]）：

python
import sys
import math
import re

def solve():
    data = sys.stdin.read().strip()
    if not data:
        return
    # 从输入中提取两个列表（形如 "[1,2,3]" 和 "[4]"）
    lists = re.findall(r'$$([^$$]*)\]', data)
    if len(lists) < 2:
        return
    def parse_list(s):
        s = s.strip()
        if not s:
            return []
        return list(map(int, s.split(',')))
    nums = parse_list(lists[0])
    target = parse_list(lists[1])
    m = len(target)
    FULL = (1 << m) - 1

    # 预计算所有非空子集（target 的下标集合）的 lcm
    # 因为 target 长度最多 4，非空子集最多 2^4 - 1 = 15 个
    cand_info = []  # 每项为 (mask, L) ，mask 表示选取了哪些 target ，L 为 lcm
    def lcm(a, b):
        return a // math.gcd(a, b) * b
    for mask in range(1, 1 << m):
        L = 1
        for j in range(m):
            if mask & (1 << j):
                L = lcm(L, target[j])
        cand_info.append((mask, L))
    
    INF = 10**18
    # dp[mask] = 最少操作次数使得已经选中的元素覆盖状态为 mask
    dp = [0] + [INF] * FULL

    # 对于 nums 中的每个元素，计算它的候选更新方案。
    # 注意：每个元素只能更新一次，所以我们对每个元素构造一个“候选方案集合”
    for x in nums:
        # 对于一个元素，可以枚举所有非空候选子集，
        # 计算 v = ceil(x / L) * L, cost = v - x
        # 然后扫描 target 数组，判断 v 能覆盖哪些目标（即 v % t == 0），得到一个掩码 cand_mask
        best = {}  # best[cand_mask] = 在本元素中选取方案使得覆盖状态为 cand_mask 的最小 cost
        for _, L in cand_info:
            # 更新到不小于 x 的最小 L 的倍数
            v = ((x + L - 1) // L) * L
            cost = v - x
            # 计算 v 能覆盖哪些 target
            cand_mask = 0
            for j in range(m):
                if v % target[j] == 0:
                    cand_mask |= (1 << j)
            # 更新最小 cost
            if cand_mask in best:
                if cost < best[cand_mask]:
                    best[cand_mask] = cost
            else:
                best[cand_mask] = cost

        # 0/1 背包更新：对于本元素的每个候选方案，
        # 对于已有的 dp 状态 state，更新 dp[state | cand_mask]
        newdp = dp[:]  # 新 dp 状态：不使用本元素的情况仍保留
        for cand_mask, cand_cost in best.items():
            # 这里遍历 dp 的 16 个状态（m<=4，所以最多 16 个）
            for prev_mask in range(FULL + 1):
                if dp[prev_mask] == INF:
                    continue
                new_mask = prev_mask | cand_mask
                new_cost = dp[prev_mask] + cand_cost
                if new_cost < newdp[new_mask]:
                    newdp[new_mask] = new_cost
        dp = newdp

    # 输出答案
    sys.stdout.write(str(dp[FULL]))

if __name__ == '__main__':
    solve()

说明

预处理候选子集
我们枚举 target 所有非空子集，计算对应的 lcm。这样对于一个元素 $x$ ，可以用公式
$v = \left\lceil \frac{x}{L} \right\rceil \times L$
得到更新后值，再计算更新次数（ $v-x$ ）。
计算“实际覆盖”
虽然我们是根据某个子集更新的，但更新后的数 $v$ 可能同时满足更多 $t$ 的倍数条件，因此遍历 target 数组计算最终覆盖掩码。
动态规划更新
用 dp 数组记录：使用部分元素后能覆盖哪些目标，以及对应的最少操作次数。每个元素只能用一次，因此更新时需要基于旧的 dp 状态。

此解法的时间复杂度大约为

O(n \cdot 2^m \cdot m)

由于 $m\le4$ ，即使 $n$ 达到 $5\times 10^4$ 也足够。

你可以直接运行以上代码来解决问题。

最少操作次数计算

Вопрос

Мысль

Ответ

说明

Поделиться этим Q&A