2208. 将数组和减半的最少操作次数
已解答
给你一个正整数数组 nums 。每一次操作中，你可以从 nums 中选择 任意 一个数并将它减小到 恰好 一半。（注意，在后续操作中你可以对减半过的数继续执行操作）
请你返回将 nums 数组和 至少 减少一半的 最少 操作数。
思路：
每次找当前数组中最大的数分成一半，再把这一半放回数组中。重复这个操作，直到数组和减小到最初的一半以下才停止。
正确性：假设最优解当前分割的是x，贪心分解的是y，则y大于x（因为贪心分解的是当前最大的数）。若y没有出现在最优解中，则把最优解的x替换成y，最优解中后续分解的x/2，x/4...通通变成y/2，y/4....，则此时一定还是在最优解次数内实现数组和减小到一半（就是每次减的都更多了，那一定是能更快或同一次数减小到一半，但是最优解就是最小次数，因此当前只能是一样的次数）。
若y出现在最优解后续步骤中，则互换最优解中x，y的位置，并且对有x到y步骤之间出现的x/2，x/4....，将y、x互换后的，x取代x/2位置，x/2取代x/4位置。。。。一直到最后一个x/k取代原本y，x互换后的x的位置，这样换完仍然是最优解，因此贪心是本题的最优解做法。
注意：本题开始将nums数组所有数字加一起可能会超出int的范围，因此用了double。
class Solution {
public:int halveArray(vector<int>& nums) {double all=0;priority_queue<double>dp;for(auto e:nums){all+=e;dp.push(e);}double cut=0;int ret=0;while(2*cut<all){//选最大的变成一半double node=dp.top();dp.pop();cut+=(node/2);dp.push(node/2);ret++;}return ret;}
};
