题目如上:
首先通过经验分析，要用最少的减半次数，使得数组总和减少至一半以上，那么第一反应就是每次都挑数组中最大的数据去减半，这样可以是每次数组总和值减少程度最大化。
代码思路:利用大根堆去找数据中的最大值，每次减半再次压入大根堆即可。
主要是如何证明贪心策略的正确性 :
我们使用《交换论证法》来证明
圆圈代表每次减半的数，圆圈的个数就代表总操作次数。
本站资源均来自互联网，仅供研究学习，禁止违法使用和商用，产生法律纠纷本站概不负责！如果侵犯了您的权益请与我们联系！
转载请注明出处： 免费源码网-免费的源码资源网站 » [c++刷题]贪心算法.N01
发表评论 取消回复