- 主题:求教 max |x1-x2|+|x2-x3|+...+|xn-x1|
已知x1,x2,...xn=1,2,...n,
求上面的绝对值之和的最大值。即
|x1-x2|+|x2-x3|+...+|x(n-1)-xn|+|xn-x1|。
这题目有个求最小值的版本,感觉挺容易。
但求最大一下子没有合适的思路了,求教各位高人,谢谢!
--
FROM 183.62.57.*
主要是怎么推出和证明这个结论?
【 在 Elale 的大作中提到: 】
: 最小值就是顺序排列,min=(n-1)*1 + (n-1)=2n-2
: 最大值就是前一半数顺序排列,后一半倒序排列然后插入到前一半数之间,即如下形式:
: 1..n..2..n-1..3..n-2..4..n-3.....i..n-i+1...
: ...................
--
FROM 183.62.57.*
谢谢!我自己也刚搞了出来,最大值跟您的做法一样。
最小值我的做法是问题等价于从1到n每个点都经过一遍又返回点1的总路程,
所以总长一定不小于2(n-1)
【 在 hound 的大作中提到: 】
: 居然要审核,我还是发个图片解答吧。
: [upload=1][/upload]
--
FROM 14.145.204.*