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;}
};