24小时热门版块排行榜

返回列表

当前只显示满足指定条件的回帖，点击这里查看本话题的所有回帖

ghw_nit

铁杆木虫 (正式写手)

应助: 14 (小学生)
金币: 7901.9
散金: 147
红花: 6
帖子: 653
在线: 175.8小时
虫号: 774851
注册: 2009-05-20
性别: GG
专业: 控制理论与方法

[求助] 已经排好序的数组的求和问题

现有一个排好序的数组，假如这个数组有n个数，此时的排序是由大到小排列的，在这n个数中任取m个数加和，这种和有什么关系呢？
假如我取5个数，那么我可以肯定的说这个数组中前五个数的和是所有的五个数的组合中最大的拿一个，那么次大的是哪一个，是不是把第五个数去掉，换成第六个数就是次大的呢，第三大的是把第五个位置换成第七个数呢，这是我的猜测，不能证明，不知道我的猜测是不是对，能不能证明这件事呢。希望有人能指点一下。谢谢

回复此楼

» 猜你喜欢

1楼 2013-06-04 22:24:06

已阅回复此楼关注TA 给TA发消息送TA红花 TA的回帖

weft

木虫 (正式写手)

应助: 125 (高中生)
金币: 2557.3
红花: 13
帖子: 301
在线: 147.4小时
虫号: 2161851
注册: 2012-12-02
专业: 文化学

【答案】应助回帖

引用回帖:

7楼: Originally posted by leungzipang at 2013-06-07 15:27:56
可以这么想：在序列中插入辅助元素，使它成为等差序列。等差的情况是好办的。
写出这个等差列的所有组合情况，把它们的和排序，然后去掉那些含有辅助元素的组合，剩下就是你要的了。

想法好是好, 但暂且先不论这么插入之后的计算复杂度(我想这是楼主最关心的), 套用一部电影的名字, 就是Mission Impossible. 看这个例子: ${2+\sqrt{2}, 2, 1}$ , 很容易证明, 不管你怎么在中间插入数字, 都不可能得到一个等差数列, 否则就与 ${\sqrt{2}}$ 是无理数相矛盾了.