【位运算 贪心】2835. 使子序列的和等于目标的最少操作次数

算法可以发掘本质，如：

一，若干师傅和徒弟互有好感，有好感的师徒可以结对学习。师傅和徒弟都只能参加一个对子。如何让对子最多。

二，有无限多1X2和2X1的骨牌，某个棋盘若干格子坏了，如何在没有坏的格子放足够多骨牌。

三，某个单色图，1表示前前景，0表示后景色。每次操作可以将一个1，变成0。如何在最少得操作情况下，使得没有两个1相邻（四连通）。

四，若干路人，有些人是熟人，如何选出最多的人参加实验。为了避免熟人影响实验的效果，参加的人不能是熟人。

一二是二分图的最大匹配，三是二分图的最小点覆盖，四是二分图最大独立集。 而这三者是等效问题。

本文涉及知识点

位运算 贪心

LeetCode 2835. 使子序列的和等于目标的最少操作次数

给你一个下标从 0 开始的数组 nums ，它包含 非负 整数，且全部为 2 的幂，同时给你一个整数 target 。

一次操作中，你必须对数组做以下修改：

选择数组中一个元素 nums[i] ，满足 nums[i] > 1 。

将 nums[i] 从数组中删除。

在 nums 的 末尾 添加 两个 数，值都为 nums[i] / 2 。

你的目标是让 nums 的一个 子序列 的元素和等于 target ，请你返回达成这一目标的 最少操作次数 。如果无法得到这样的子序列，请你返回 -1 。

数组中一个 子序列 是通过删除原数组中一些元素，并且不改变剩余元素顺序得到的剩余数组。

示例 1：

输入：nums = [1,2,8], target = 7

输出：1

解释：第一次操作中，我们选择元素 nums[2] 。数组变为 nums = [1,2,4,4] 。

这时候，nums 包含子序列 [1,2,4] ，和为 7 。

无法通过更少的操作得到和为 7 的子序列。

示例 2：

输入：nums = [1,32,1,2], target = 12

输出：2

解释：第一次操作中，我们选择元素 nums[1] 。数组变为 nums = [1,1,2,16,16] 。

第二次操作中，我们选择元素 nums[3] 。数组变为 nums = [1,1,2,16,8,8] 。

这时候，nums 包含子序列 [1,1,2,8] ，和为 12 。

无法通过更少的操作得到和为 12 的子序列。

示例 3：

输入：nums = [1,32,1], target = 35

输出：-1

解释：无法得到和为 35 的子序列。

提示：

1 <= nums.length <= 1000

1 <= nums[i] <= 2³⁰

nums 只包含非负整数，且均为 2 的幂。

1 <= target < 2³¹

位运算

target可以拆分成 2ⁱ¹+2ⁱ²+⋯ \cdots⋯ + 2 ⁱⁿ

性质一：如果2^j1+2^j2… \dots…+2^jm >= 2ⁱ 且 j1到jm都小于等于i。

则一定可以从 j1,j2⋯ \cdots⋯jm 中选择若干数，使得其和等于2ⁱ。

证明：

i = 0 时 。 2⁰=2⁰.

x>=1，如果i=x，性质一成立，则i=x+1，性质一也成立。

由于左式 >= 2^x+1 > 2^x 故左式可以抽取s = 2^x

左式 - S >= 2^x,故还可以抽取S2 = 2^x

S+S2和在一起，就是2^x+1

性质二：

如果Ti大于等于targeti    ⟺    \iff⟺ 本题

情况一：target只有一项，就是性质一。

情况二：如果target有x项成立，则x+1项也成立。移除x项后，就成了性质一。

解法

通过i从低位到高位枚举target，其和记录到：iNeed。

cur = 1 << i 。

nums中小于等于cur的加到llHas中。

如果 llHas < iNeed， 则拆分nums中的最小元素next到cur，如果无元素可拆分，则返回-1。

拆分后：一个cur加到llHas, next/2 next/4 … \dots… cur 加到setNum。

本解法用的多键集合，其实用大根堆 更简洁。

代码

核心代码

class Solution {
public:
  int minOperations(vector<int>& nums, int target) {
    std::multiset<int> setNum(nums.begin(), nums.end());
    int iRet = 0;
    long long llHas = 0;
    int iNeed = 0;
    for (int i = 0; i <= 30; i++) {
      const int cur = 1 << i;
      while (setNum.size() && (*setNum.begin() <= cur)) {
        llHas += *setNum.begin();
        setNum.erase(setNum.begin());
      }
      if (cur & target) {
        iNeed += cur;
      }
      while (llHas < iNeed) {
        auto it = setNum.lower_bound(cur);
        if (setNum.end() == it) { return -1; }
        int next = *it;
        setNum.erase(it);       
        while (cur != next) {
          next /= 2;
          setNum.emplace(next);
          iRet++;
        }
        llHas += cur;
      } 
    }
    return iRet;
  }
};

测试用例

template<class T>
void Assert(const T& t1, const T& t2)
{
  assert(t1 == t2);
}
template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
  if (v1.size() != v2.size())
  {
    assert(false);
    return;
  }
  for (int i = 0; i < v1.size(); i++)
  {
    Assert(v1[i], v2[i]);
  }
}
int main()
{ 
  vector<int> nums; int target;
  {
    Solution sln;
    nums = { 1, 2, 8 }, target = 7;
    auto res = sln.minOperations(nums, target);
    Assert(1, res);
  }
  {
    Solution sln;
    nums = { 1, 32, 1, 2 }, target = 12;
    auto res = sln.minOperations(nums, target);
    Assert(2, res);
  }
  {
    Solution sln;
    nums = { 1,32,1 }, target = 35;
    auto res = sln.minOperations(nums, target);
    Assert(-1, res);
  }
  
}

测试环境

操作系统：win7 开发环境： VS2019 C++17

或者 操作系统：win10 开发环境： VS2022 C++17

如无特殊说明，本算法用**C++**实现。