力扣题解（将数组和减半的最小操作次数）
已解答
给你一个正整数数组 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;
}
};原文地址：https://blog.csdn.net/yyssas/article/details/140640798
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！