请教一个算法问题

N个整数，正负皆可，现需要将其合并为一个数，合并规则为：两个数合并后值取两数和的一半，比如-8和5合并后为1.5；合并后的数字可以继续和其他数或其他合并后的数字合并，比如数列-2,2,3,8，-2和2合并后的0可以继续和3合并得到1.5，也可以和3、8合并后的2.5合并得到1.25。
问合并后最大值以及取得最大值的合并组合。

最大值4.75，组合是(((-2 + 2)/2 + 3)/2 + 8) / 2，我猜的

不感兴趣

开通SVIP免广告

个人感觉取最大值方法是先让小数合并然后合并大数，这样小数的计算的基数就会少一些，
比如说你说的-2 2 3 8
按小数先合并的思想就是4.75=-2/8+2/8+3/4+8/2
可以看到先结合的数占的比重为还剩下结合次数为2，那权值就为1/（2^3）
这样这个问题就可以接了
先找出最小的两个数然后结合，继续找最小的数来结合，直到所有数都结合完就行了

两种方法
1，建堆 O（nlgn）
2.寻找规律 O（n)

扫二维码下载贴吧客户端

下载贴吧APP
看高清直播、视频！

17回复贴，共1页

<<返回c语言吧

分享到:

日	一	二	三	四	五	六