网页资讯视频图片知道文库贴吧地图采购
进入贴吧全吧搜索
c语言吧 关注：799,001贴子：4,352,623
  • 17回复贴，共1页

请教一个算法问题

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，我猜的


个人感觉取最大值方法是先让小数合并 然后合并大数，这样小数的计算的基数就会少一些，
比如说你说的-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页
分享到: