使子序列的和等于目标的最小操作次数-526互联

给你一个下标从 0 开始的数组 nums ，它包含非负整数，且全部为 2 的幂，同时给你一个整数 target 。
一次操作中，你必须对数组做以下修改：

选择数组中一个元素 nums[i] ，满足 nums[i] > 1 。
将 nums[i] 从数组中删除。
在 nums 的末尾添加两个数，值都为 nums[i] / 2 。

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

1. 哈希

子序列意味着可以使用任意数组合，其实该题就是用数来凑出target对应二进制的所有位，小的可以凑出大的，不需要代价，而大的拆分成小的需要代价，所以贪心的从低位开始

class Solution {
public:
    int minOperations(vector<int>& nums, int target) {
        //使得数组中存在对应二进制
        if(accumulate(nums.begin(),nums.end(),0ll)<target) return -1;
        vector<int> cur(32);
        vector<bool> goal(32);
        for(int i=0;i<32&&target;i++){//拆分成各位需要的数
            goal[i] = target%2;
            target/=2;
        }
        for(int i=0;i<nums.size();i++) //该位具有的个数
            cur[log2(nums[i])]++;
        int res = 0;//记录需要借的次数
        for(int i=0;i<31;i++){ //后面借一个就足以填补前面所有位
            cur[i]-=goal[i];//进行分配
            if(cur[i]>0) cur[i+1] += cur[i]/2;//多余的凑上去
            else if(cur[i]<0){
                res++;//借一次
                cur[i+1]-=1;//最多借一个
            }
        }
        if(cur[31]<0) return -1;//不够借
        return res;
    }
};