位运算|拆分贪心

lc2835

给一个全是2的幂的非负整数数组和目标值，可将数组中大于1的元素拆成两个其1/2的数（算一次操作）

求让数组存在和为目标值的子序列的最少操作次数，无法实现则返回-1。

统计+手动进位

统计数组元素的二进制幂次计数，

累加幂次和并与目标值二进制分段比对，不足时拆分更大幂次元素补充

统计拆分操作次数得到最小操作数

class Solution {
public:
int minOperations(vector<int>& nums, int target) {
if (accumulate(nums.begin(), nums.end(), 0LL) < target) {
return -1;
}
int cnt[31]{};
for (int x : nums) {
cnt[__builtin_ctz(x)]++;
}
int ans = 0, i = 0;
long long s = 0;
while ((1LL << i) <= target) {
s += (long long) cnt[i] << i;
int mask = (1LL << ++i) - 1;
if (s >= (target & mask)) {
continue;
}
ans++; // 一定要找更大的数操作
for (; cnt[i] == 0; i++) {
ans++; // 还没找到，继续找更大的数
}
}
return ans;
}
};