企业网站建设ppt模板晋中市科技馆网站建设

题目如上:

首先通过经验分析，要用最少的减半次数，使得数组总和减少至一半以上，那么第一反应就是每次都挑数组中最大的数据去减半，这样可以是每次数组总和值减少程度最大化。

代码思路:利用大根堆去找数据中的最大值，每次减半再次压入大根堆即可。

主要是如何证明贪心策略的正确性 :

我们使用《交换论证法》来证明

圆圈代表每次减半的数，圆圈的个数就代表总操作次数。