3489. 零数组变换 IV

发表于 分类于 阅读次数： Waline： 本文字数： 907 阅读时长 ≈ 3 分钟

考点

  • 01背包
  • 多重背包
  • 二分

思路

对于输入样例

1
nums = [1,2,3,2,1], queries = [[0,1,1],[1,2,1],[2,3,2],[3,4,1],[4,4,1]]

画图可以发现，该题有两种思路

二分+多重背包(竖着看)

二分前缀长度 mid，问只用前 mid 个查询能否把数组清零

如果可行，向左收缩；否则向右扩张

单次可行性检查 check(mid) 的关键在于： 对每个 i，我们只需要知道在前 mid 个查询中覆盖 i 的各个 val（1..10）分别出现了多少次

因为对同一个 val，可用次数是有限的（多重背包），我们要做的是多重背包的子集和：选不超过 cnt[v] 个值为 v 的物品，使和为 nums[i]

按上述思路可以写出第一版AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
class Solution {
public:
    int minZeroArray(vector<int>& nums, vector<vector<int>>& queries) {
        int n = nums.size(), m = queries.size();
        auto check = [&](int mid) -> bool {
            for (int i = 0; i < n; ++i) {
                if (nums[i] == 0)
                    continue;
                unordered_map<int, int> mp;
                bool f[1001];
                memset(f, 0, sizeof(f));
                f[0] = 1;
                for (int j = 0; j < mid; ++j) {
                    int l = queries[j][0], r = queries[j][1], v = queries[j][2];
                    if (l <= i && i <= r)
                        mp[v]++;
                }
                for (auto it : mp) {
                    int val = it.first, cnt = it.second;
                    int j = 1, s = 1;
                    while (s <= cnt) {
                        for (int k = 1000 - val * j; k >= 0; --k) {
                            if (f[k])
                                f[k + val * j] = 1;
                        }
                        j <<= 1;
                        s += j;
                    }
                    s -= j;
                    if (s <= cnt) {
                        j = cnt - s;
                        for (int k = 1000 - val * j; k >= 0; --k) {
                            if (f[k])
                                f[k + val * j] = 1;
                        }
                    }
                }
                if (!f[nums[i]])
                    return 0;
            }
            return 1;
        };

        int l = 0, r = m + 1;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (check(mid))
                r = mid;
            else
                l = mid + 1;
        }
        if (l == m + 1)
            return -1;
        return l;
    }
};

进行二次优化后得到第二版AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
 public:
  int minZeroArray(vector<int>& nums, vector<vector<int>>& queries) {
    int n = nums.size(), m = queries.size();
    auto check = [&](int mid) -> bool {
      for (int i = 0; i < n; ++i) {
        int x = nums[i];
        if (x == 0) continue;
        // 统计多重背包
        // cnt[v]: 价值v的物品有多少个
        int cnt[11];
        memset(cnt, 0, sizeof(cnt));
        for (int j = 0; j < mid; ++j) {
          int l = queries[j][0], r = queries[j][1], v = queries[j][2];
          if (l <= i && i <= r) cnt[v]++;
        }
        // 对每个i执行多重背包, 二进制优化+位运算优化
        bitset<1001> f;
        f[0] = 1;
        for (int v = 1; v <= 10 && !f[x]; ++v) {
          int  c = cnt[v];
          for (int k = 1; c > 0 && !f[x]; k <<= 1) {
            int mi = min(k, c), w = mi * v;
            f |= f << w;
            c -= k;
          }
        }
        if (!f[x]) return false;
      }
      return true;
    };
    // 二分, 如果最终停留在m + 1上, 说明所有访问序列都没办法变成0
    int l = 0, r = m + 1;
    while (l < r) {
      int mid = (l + r) >> 1;
      if (check(mid))
        r = mid;
      else
        l = mid + 1;
    }
    if (l == m + 1) return -1;
    return l;
  }
};

01背包(横着看)

把每个下标 \(i\) 视为独立问题：

仅考虑所有覆盖它的查询的 val，问能不能从这些 val 里选若干个，使和正好等于 nums[i]

容易得到第一版AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
    int minZeroArray(vector<int>& nums, vector<vector<int>>& queries) {
        const int maxn = 1e3;
        int n = nums.size(), m = queries.size(), ans = -1;
        bool f[maxn + 1];
        for (int i = 0; i < n; ++i) {
            memset(f, 0, sizeof(f));
            int x = nums[i];
            if (x == 0) {
                ans = max(ans, 0);
                continue;
            }
            f[0] = 1;
            int res = -1;
            for (int j = 0; j < m; ++j) {
                int l = queries[j][0], r = queries[j][1], v = queries[j][2];
                if (l <= i && i <= r) {
                    for (int k = maxn - v; k >= 0; --k) {
                        if (f[k])
                            f[k + v] = 1;
                    }
                }
                if (f[x]) {
                    res = max(res, j + 1);
                    break;
                }
            }
            if (res == -1)
                return -1;
            else
                ans = max(ans, res);
        }
        return ans;
    }
};

然后位运算进行优化，得到第二版：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    int minZeroArray(vector<int>& nums, vector<vector<int>>& queries) {
        const int maxn = 1e3;
        int n = nums.size(), m = queries.size(), ans = -1;
        for (int i = 0; i < n; ++i) {
            int x = nums[i];
            if (x == 0) {
                ans = max(ans, 0);
                continue;
            }
            bitset<maxn + 1> f;
            f[0] = 1;
            int res = -1;
            for (int j = 0; j < m; ++j) {
                int l = queries[j][0], r = queries[j][1], v = queries[j][2];
                if (l <= i && i <= r) {
                    f |= f << v;
                }
                if (f[x]) {
                    res = max(res, j + 1);
                    break;
                }
            }
            if (res == -1)
                return -1;
            ans = max(ans, res);
        }
        return ans;
    }
};