使子序列的和等于目标的最少操作次数
给你一个下标从 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^{30}\)
nums 只包含非负整数，且均为 2 的幂。
\(1 <= target < 2^{31}\)
解题思路
见代码注释。
c++由于是强类型语言，所以需要注意数据溢出的问题，比如int和long long int，要是以后实在找不到哪里溢出还是直接python吧orz。学到了一个c++的新语法：1LL，可以告诉编译器将1解释为long long int。
code
class Solution:
'''
1. 什么情况下结果不存在
sum(nums) < target时结果不存在;
如果sum(nums) >= target,那么最糟糕的情况是全部拆分为1，也是可以有解的
2.通过二进制的方式思考(2的幂)
3.从低位到高位思考
要求的是最小的操作次数，那么最好的情况就是可以使用现有的数组元素构造出target目标元素，退而求其次就是需要使用
数组元素构造出target中的一部分，也就是需要从低到高进行构建
数组中的所有小于等于2^i的元素和>=2^i,能否不操作构造出2^i
1.可以的，通过数学归纳法可以证明
2^0=1 -> s>=1,那么必然是有1的，可以直接构造得出
2^1=2 -> s>=2,如果有2，直接可以构造，如果没有2，那么至少有两个1，可以构造
2^2=4 -> s>=4,如果有4，直接可以构造，如果没有4，那么数组中的元素都是<=2的，通过第二点可知，可以构造出一
个2，同时由于s>=4,那么剩余的结果>=2,根据2还是可以构造出一个，最后构造出4
……
2^k -> s >= 2^k可以构造出
2^k+1 -> 2 >= 2^k+1,如果有2^k+1,那么可以直接构造出结果,如果不存在，那么数组中的元素都是<=2^k的，通过上
一点可知可以构造出一个2^k，在构造出一个2^k后，剩余的结果是>=2^k的，还可以构造出一个2^k,最后构造出结果
2. 算法过程
遍历target的每一个二进制位，1则尝试构造，0则不用考虑
1. 计算s,如果s >= 2^i,可以直接构造,从s中减去2^i
2. 如果s<2^i,需要从比2^i大的数2^j中进行拆分
拆分可以得到2^j-1,2^j-2.....2^i+1,2^i,2^i
可以看到：
1.操作次数为j - i
2.不仅得到i,还有j-1,j-2,....,i+1,也就是下一位可以从j开始
3.这里想不明白的因为涉及到s的加减，可以直接构造的话要减去，不可以直接构造的话得拆分，拆分后s应当如何
计算如果从j开始的话
4.所以还是朴素写法吧，不要直接跳，有点想不明白怎么写
'''
def minOperations(self, nums: List[int], target: int) -> int:
if(sum(nums) < target):
return -1
cnt = Counter(nums)
ans = s = i = 0
flag = 0
while((1 << i) <= target):
s += cnt[1<<i] * (1 << i)
if((target>>i) & 1):
if(s >= (1<<i)):
s -= (1<<i)
i += 1
continue
#查找比1<<i大的数
j = i + 1
while(cnt[1<<j] == 0):
j += 1
ans += j - i
for k in range(i,j):
cnt[1<<k] += 1
cnt[1<<j] -= 1
s += 1 <<i
i += 1
else:
i += 1
return ans
class Solution {
public:
int minOperations(vector<int>& nums, int target) {
long long int sum = 0;
for(auto item : nums) sum += item;
if(sum < target) return -1;
unordered_map<int,int> cnt;
for(auto item : nums) cnt[item]++;
int ans = 0,i = 0;
long long int s = 0;
while((1LL<<i) <= target)
{
cout<<i<<endl;
s += (long long int)cnt[1<<i] * (long long int)(1<<i);
if((target>>i) & 1)
{
if(s >= (1<<i))
{
s -= 1 << i;
i ++;
continue;
}
int j = i + 1;
//cout<<(1<<i)<<" "<<j<<endl;
while(cnt.find(1<<j) == cnt.end())
{
//cout<<"in?"<<endl;
j++;
}
ans += j - i;
for(int k = i;k < j;k++) cnt[1<<k] ++;
cnt[1 << j] --;
s += 1 << i;
i ++;
//cout<<i<<(1<<i)<<endl;
}
else i ++;
}
return ans;
}
};