将数组和减半的最少操作次数(贪心)

问题描述

给你一个正整数数组 nums 。每一次操作中，你可以从 nums 中选择 任意 一个数并将它减小到 恰好 一半。（注意，在后续操作中你可以对减半过的数继续执行操作）
请你返回将 nums 数组和 至少 减少一半的 最少 操作数。

解题思路

采取贪心策略来解决这个问题。那么什么情况下是局部最优解呢？
很显然，一次操作中，将数组中最大数减半是使得数组之和减少最多的。换言之，这就是我们所求的局部最优解。
那么明确了贪心策略之后，我们的算法就是通过对数组最大值不断减半来实现。

算法实现

class Solution {
public:int halveArray(vector<int>& nums){priority_queue<double>heap;int count = 0;double mins = 0, sum = 0;for (auto& e : nums){heap.push(e);sum += e;}while (mins < sum/2){double t = heap.top();heap.pop();t /= 2;mins += t;count++;heap.push(t);}return count;}
};
int main()
{vector<double>arr(10);double sum = 0, ans = 0;for (int i = 0; i < 10; i++){cin >> arr[i];sum += arr[i];}sum /= 10;for (int i = 0; i < 10; i++){ans += (arr[i] - sum) * (arr[i] - sum);}cout << sum << endl<< ans / 9 << endl;return 0;
}

正确性证明

这里依旧采用交换论证法。
对于最优策略a1，a2,…,an,贪心策略b1,b2,…,bn。
考虑两种策略前k-1项相同，第k项不同。此时存在两种情况：
1.不存在am=bk,m>k。则考虑将ak转换成bk，由于bk操作使得数组减少量大于ak操作，即保证了正确性不发生改变。
2.存在am=bk,m>k。交换am和ak，但由于存在al，k<l<m使用的是原ak减半后的操作数。故需要将al与am交换，若重复出现该情况则继续交换。不难发现单纯的操作顺序变换不会使得正确性发生变化。

重复上述操作使得最优策略a1，a2,…,an转换为贪心策略b1,b2,…,bn。
即正确性得证。