2025-09-16：零数组变换Ⅳ。用go语言，给定一个长度为 n 的整数数组 nums 和若干查询 queries，其中每个查询用三元组 [li, ri, vali] 表示一次操作规则：

• 对于该查询，你可以在下标区间 [li, ri] 里任选一些位置（也可以不选），把这些位置上的元素各自减去相同的数值 vali。

目标是按查询给出的顺序依次执行前 k 次操作（对于每次操作可以自由选择区间内的下标集合），使得最终数组中所有元素都变为 0。要求找出满足这一条件的最小非负整数 k；如果不存在任何 k 能达到这个目标，返回 -1。

1 <= nums.length <= 10。

0 <= nums[i] <= 1000。

1 <= queries.length <= 1000。

queries[i] = [li, ri, vali]。

0 <= li <= ri < nums.length。

1 <= vali <= 10。

输入： nums = [1,2,3,2,6], queries = [[0,1,1],[0,2,1],[1,4,2],[4,4,4],[3,4,1],[4,4,5]]。

输出： 4。

问题描述

给定一个整数数组 nums 和一系列查询 queries，每个查询是一个三元组 [li, ri, vali]，表示可以在下标区间 [li, ri] 内任意选择一些位置（可以不选），将这些位置上的元素减去 vali。目标是按顺序执行前 k 次操作（每次操作可以自由选择区间内的下标集合），使得最终数组所有元素变为0。要求找出最小的非负整数 k（即使用前 k 个查询），如果无法实现则返回-1。

解决思路

1. 问题分析：每个查询操作相当于提供了一种“资源”（即可以减去某个值 vali），但该资源只能应用于特定区间内的元素。对于每个非零元素 nums[i]，我们需要通过一系列操作（即选择一些查询）来恰好减去 nums[i]。注意，每次操作（查询）可以自由选择区间内的下标，因此同一个操作可以被多个元素使用（但每次使用只能减去固定的 vali），但每个元素需要减去多个不同的 vali（来自不同的操作）来达到0。

2. 关键观察：对于每个位置 i（其初始值为 nums[i]），我们需要从查询集合中选出一个子集（这些查询必须覆盖位置 i，即 li <= i <= ri），并且这些查询的 vali 通过某种组合（每个查询可以使用多次，但最多不超过它在查询中出现的次数？实际上，每个查询只能使用一次，但每次使用可以应用于多个位置？注意：每次操作（查询）可以自由选择区间内的任意下标集合（包括空集），因此同一个操作可以被多个元素使用（但每个操作只能使用一次？实际上，对于同一个操作，我们可以选择在多个位置上应用，但每个位置只能被同一个操作减去一次？但这里每次操作（查询）的规则是：在区间内任选一些位置，每个位置减去相同的 vali。因此，同一个操作可以同时被多个位置使用（即同时减去多个位置的值），但每个位置只能被同一个操作减去一次（因为一次操作中，对于同一个位置，要么被减去 vali，要么不被减）。所以，对于每个位置 i，它可以使用多个操作（只要这些操作覆盖了 i），每个操作最多使用一次（但同一个操作可以被多个位置共享使用）。

   实际上，问题可以转化为：对于每个位置 i，我们需要从覆盖了 i 的查询中选出一个多重集（每个查询最多选一次？但注意：同一个查询可以被多个位置共享使用（即同一个操作可以同时减去多个位置的值），但每个位置使用同一个查询只能一次（因为一次操作中，对于同一个位置只能减去一次）。因此，对于每个位置 i，它需要从覆盖它的查询中选取一些查询（每个查询最多用一次），这些查询的 vali 的和（实际上不是简单的和，而是每个查询贡献一个 vali，但需要组合成恰好 nums[i]？注意：每个查询的 vali 是固定的，但我们可以选择使用或不使用该查询（即是否在位置 i 上应用这个操作）。因此，每个位置 i 的需求是：从覆盖它的查询中选出一个子集，使得这些查询的 vali 的和等于 nums[i]？不对，因为同一个查询的 vali 只能使用一次（但可以被多个位置使用），所以对于位置 i，它需要从覆盖它的查询中选取一些查询（每个查询最多选一次），这些查询的 vali 的和等于 nums[i]？但这里允许同一个查询被多个位置使用（即多个位置可以同时使用同一个查询），所以每个查询可以被多个位置使用，但每个位置只能使用一次每个查询。

   然而，实际上，每个查询操作（即每个三元组）只能执行一次（即我们按顺序执行前k个查询），但执行时可以选择在哪些位置上应用（即可以应用于多个位置）。因此，对于每个查询，它可以被多个位置使用（即多个位置都可以在这次操作中被减去 vali），但每个位置只能使用同一个查询一次（因为一次操作中，对于同一个位置要么减要么不减）。所以，对于每个位置 i，它可以使用多个查询（这些查询必须覆盖i），每个查询最多使用一次（即要么在位置i上应用该操作，要么不应用）。因此，位置i的需求是：从覆盖它的查询中选出一个子集（每个查询最多选一次），使得这些查询的 vali 的和等于 nums[i]？注意：这里每个查询的 vali 是固定的，所以确实是一个子集和问题。

   但是，这里有一个重要点：同一个查询可以被多个位置使用（即多个位置都可以在同一个查询操作中被减去 vali），所以不同位置之间可以共享同一个查询（即同一个查询可以同时被多个位置使用）。因此，整个问题可以分解为：对于每个位置i，我们需要从覆盖它的查询中选出一个子集（每个查询最多用一次），使得子集的 vali 和等于 nums[i]。并且，这些选择不能冲突（即同一个查询可以被多个位置使用，但每个位置只能使用一次每个查询）？实际上，这里没有冲突：因为同一个查询可以被多个位置同时使用（即一次操作可以同时减去多个位置的值），所以每个位置独立地选择覆盖它的查询（只要每个查询的 vali 是固定的），并且这些选择是兼容的（因为同一个查询可以被多个位置使用）。

   因此，问题变成：对于每个位置i，要求覆盖它的查询中存在一个子集，其 vali 的和等于 nums[i]。并且，这些子集可以共享同一个查询（即同一个查询可以出现在多个位置的子集中）。所以，实际上每个位置的需求是独立的？但注意：查询是按顺序执行的，并且我们只能使用前k个查询。

3. 二分搜索：我们使用二分搜索来寻找最小的k（0到len(queries)+1），使得前k个查询能够满足所有位置的需求（即对于每个位置i，存在一个覆盖它的查询子集（来自前k个查询），其 vali 的和等于 nums[i]）。

4. 验证函数（二分搜索的内部）：对于给定的k（即使用前k个查询），检查是否所有位置i（其中nums[i] != 0）都能被满足：

   • 对于每个位置i（nums[i] != 0），收集所有覆盖i的前k个查询（即查询的区间[li, ri]包含i，且查询的索引小于k）。
   • 对于这些查询，每个查询提供一个价值为 vali 的“物品”，并且每个查询的数量是1（但注意：同一个查询可以被多个位置使用，所以对于单个位置i来说，每个查询只能使用一次）。因此，对于位置i，问题转化为：从这些查询（物品）中选出一个子集，使得子集的和恰好为nums[i]？但这里每个查询（物品）的“体积”是vali，并且每个物品只有一个（但注意：实际上同一个查询可以被多个位置使用，所以对于单个位置i的限制是每个查询最多用一次？但这里我们只考虑一个位置i，所以确实每个查询最多只能选一次（即要么在位置i上应用该操作，要么不应用）。所以是01背包？但注意：每个查询的vali可能相同，所以可能有多个查询具有相同的vali？因此，对于位置i，我们实际上有多个物品（每个覆盖i的查询就是一个物品），物品的价值是vali，且每个物品只有一个。所以这是一个01背包问题？但物品数量最多为k（即前k个查询中覆盖i的查询数量），而背包容量为nums[i]（最大1000）。但k最大1000，nums[i]最大1000，所以直接01背包（O(ncapacity)）是可行的？但这里n是覆盖i的查询数量，最多1000，容量1000，所以最多10^6次操作 per position？但总共有10个位置，所以总验证次数最多1010^6=10^7，在Go中可能可行。

   然而，代码中使用了多重背包的二进制优化（但为什么？）因为实际上，对于同一个vali值，可能有多个查询（即多个物品具有相同的价值vali）。因此，我们可以将相同vali的物品分组，形成多重背包？但注意：每个查询是独立的（即使vali相同），所以实际上每个物品都是独立的（因为每个查询对应一个物品），所以应该是01背包？但代码中却使用了多重背包的二进制优化：它将相同vali值的查询分组（计数），然后使用二进制优化（将相同价值的物品分组，然后拆分成2的幂次个）来优化。这是因为对于同一个vali值，如果有多个查询，那么这些查询是相同的物品（价值相同），所以可以合并（但注意：这些查询是不同的操作，但对于位置i来说，它们的效果相同（都是减去vali），所以确实可以视为相同物品？但这里每个查询只能被使用一次（对于位置i来说），所以实际上就是多重背包（有多个相同价值的物品）？因此，对于每个vali值（从1到10），我们统计覆盖i的查询中vali等于该值的查询数量（即物品的数量）。然后，使用二进制优化将多重背包转化为01背包。

   具体地，对于位置i，我们有一个背包容量为nums[i]，以及10种物品（vali从1到10），每种物品有cnt[v]个。我们需要判断是否可以从这些物品中选出一个子集，使得恰好装满背包（即价值和等于nums[i]）。

5. 使用大整数（big.Int）表示背包状态：为了高效地进行背包DP，代码中使用了一个大整数f（看作一个bitset），其中第j位为1表示背包容量j可以被恰好装满。初始化f=1（即容量0可以被装满）。然后，对于每种价值v，我们将其物品数量进行二进制拆分（例如，有5个价值为v的物品，则拆成1个、2个、2个？二进制拆分：1,2,2确实可以表示0~5），然后每次加入一个“大物品”（大小为vk，其中k是拆分出的数量）。通过左移和OR操作来更新状态（即加入一个大小为vk的物品，相当于将当前状态左移v*k位然后OR）。最后检查f的第nums[i]位是否为1（即容量nums[i]能否被装满）。

6. 验证过程：对于每个非零元素nums[i]，我们执行上述的多重背包（二进制优化）判断。如果所有位置都能被满足，则k可行；否则不可行。

7. 二分搜索范围：k从0到len(queries)（包括），所以二分搜索最多进行log2(1000)≈10次。每次验证需要处理所有非零位置（最多10个），每个位置处理最多10种物品（每种物品二进制拆分后最多log2(1000)≈10组），所以总验证次数为10（二分次数）*10（位置）*10（物品种类）*10（二进制拆分组数）≈10000次操作（但实际中背包状态用bitset操作，左移和OR操作很快）。

时间复杂度

• 二分搜索：O(log(Q))，其中Q是查询数量（最多1000，所以二分大约10次）。
• 每次验证：遍历所有位置（最多10个），对于每个位置，收集覆盖它的查询（但这里没有显式遍历所有查询？实际上，代码中对于每个位置i，遍历前k个查询来统计每个vali的出现次数？这需要O(k) per position，所以总验证中收集查询需要O(10*k)）。
• 然后对于每个位置，进行多重背包的二进制优化：物品种类为10（vali从1到10），每种物品二进制拆分成O(log(cnt))组（最多log(1000)≈10组），所以总组数最多100组？然后对于每组，进行bitset的左移和OR操作（bitset长度为nums[i]+1，最大1001，所以每次左移和OR操作的时间复杂度可以看作O(1)？因为bitset用大整数实现，但实际操作时间与位数有关，但这里位数只有1001，所以可以视为常数时间）。
• 因此，每次验证的总时间复杂度为O(10 * k + 10 * 100) = O(k)（因为k最大1000，所以每次验证大约10*1000 + 1000 = 11000次操作？）。
• 总时间复杂度：二分次数 * 每次验证时间 = O(log(Q) * (10 * k)) = O(10 * 1000 * 10) = 100000（最坏情况下）。

空间复杂度

• 主要空间是存储nums和queries：O(n + Q) = O(10+1000)=1010。
• 验证过程中，对于每个位置，统计cnt数组（大小11）和背包状态（一个大整数，大约1001位，所以空间O(1)？因为固定大小）。
• 因此总额外空间复杂度为O(n + Q)。

Go完整代码如下：

package main

import (
	"fmt"
	"math/big"
	"sort"
)

func minZeroArray(nums []int, queries [][]int) int {
	ans := sort.Search(len(queries)+1, func(mx int) bool {
		p := new(big.Int)
	next:
		for i, x := range nums {
			if x == 0 {
				continue
			}
			cnt := [11]int{}
			for _, q := range queries[:mx] {
				if q[0] <= i && i <= q[1] {
					cnt[q[2]]++
				}
			}
			// 多重背包（二进制优化）
			f := big.NewInt(1)
			for v, num := range cnt {
				for pow2 := 1; num > 0; pow2 *= 2 {
					k := min(pow2, num)
					f.Or(f, p.Lsh(f, uint(v*k))) // 视作一个大小为 v*k 的物品
					if f.Bit(x) > 0 {
						continue next
					}
					num -= k
				}
			}
			return false
		}
		return true
	})
	if ans <= len(queries) {
		return ans
	}
	return -1
}

func main() {
	nums := []int{1, 2, 3, 2, 6}
	queries := [][]int{{0, 1, 1}, {0, 2, 1}, {1, 4, 2}, {4, 4, 4}, {3, 4, 1}, {4, 4, 5}}
	result := minZeroArray(nums, queries)
	fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

def min_zero_array(nums, queries):
    def feasible(mx):
        # 判断使用前 mx 个查询能否把 nums 全部变成 0
        for i, x in enumerate(nums):
            if x == 0:
                continue
            # 统计在前 mx 个查询中覆盖位置 i 的每个 vali 的次数
            cnt = {}
            for q in queries[:mx]:
                l, r, v = q
                if l <= i <= r:
                    cnt[v] = cnt.get(v, 0) + 1
            # 位集 DP，f 的第 t 位为 1 表示可以凑出和 t
            f = 1  # 只有和 0 可达
            # 多重背包（按每个价值 v 做二进制拆分）
            reachable = False
            for v, num in cnt.items():
                pow2 = 1
                while num > 0:
                    k = pow2 if pow2 <= num else num
                    shift = v * k
                    f |= (f << shift)
                    if ((f >> x) & 1) != 0:
                        reachable = True
                        break
                    num -= k
                    pow2 <<= 1
                if reachable:
                    break
            if not ((f >> x) & 1):
                return False
        return True

    # 二分最小的 mx (0..len(queries))
    lo, hi = 0, len(queries)
    ans = -1
    while lo <= hi:
        mid = (lo + hi) // 2
        if feasible(mid):
            ans = mid
            hi = mid - 1
        else:
            lo = mid + 1
    return ans if ans is not None and ans != -1 else -1

if __name__ == "__main__":
    nums = [1, 2, 3, 2, 6]
    queries = [[0, 1, 1], [0, 2, 1], [1, 4, 2], [4, 4, 4], [3, 4, 1], [4, 4, 5]]
    print(min_zero_array(nums, queries))