水木社区手机版
- 主题:求教 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.* - 最小值就是顺序排列，min=(n-1)*1 + (n-1)=2n-2
最大值就是前一半数顺序排列，后一半倒序排列然后插入到前一半数之间，即如下形式：
1..n..2..n-1..3..n-2..4..n-3.....i..n-i+1...
则max=n(n-1)/2+[n/2](下取整)
【 在 Kordan 的大作中提到: 】
: 已知x1,x2,...xn=1,2,...n，求上面的绝对值之和的最大值。即|x1-x2|+|x2-x3|+...+|x ...
--
FROM 167.220.233.* - 主要是怎么推出和证明这个结论？
【 在 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.* - 再最问下，分别取得等号各有多少种排列？
【 在 Kordan 的大作中提到: 】
: 已知x1,x2,...xn=1,2,...n，
: 求上面的绝对值之和的最大值。即
:
: |x1-x2|+|x2-x3|+...+|x(n-1)-xn|+|xn-x1|。
:
: 这题目有个求最小值的版本，感觉挺容易。
: 但求最大一下子没有合适的思路了，求教各位高人，谢谢
: ..................
发自「今日水木 on iPhone 13 Pro」
--
FROM 101.90.148.15 - 居然要审核，我还是发个图片解答吧。
【 在 Kordan 的大作中提到: 】
: 主要是怎么推出和证明这个结论？
--
修改:hound FROM 114.93.82.253
FROM 114.93.82.253 - 谢谢！我自己也刚搞了出来，最大值跟您的做法一样。
最小值我的做法是问题等价于从1到n每个点都经过一遍又返回点1的总路程，
所以总长一定不小于2(n-1)
【 在 hound 的大作中提到: 】
: 居然要审核，我还是发个图片解答吧。
: [upload=1][/upload]
--
FROM 14.145.204.* - 这其实是一道物理题， 将x1、 x2、 x3...xn 看成x轴上的n个点，由于对称性不妨设x1=1。质点按照x1、x2、x3...的顺序移动，最后回到x1, 那么质点的位移为0， 路程就是题中的式子，这道题的本质就是求路程的最大值和最小值。 显然，质点不要来回往返移动，按照一个方向移动，最后回到x1时，路程最小。 反之，质点尽可能远的往返移动，路程最长。
【 在 Kordan 的大作中提到: 】
: 已知x1,x2,...xn=1,2,...n，
: 求上面的绝对值之和的最大值。即
: |x1-x2|+|x2-x3|+...+|x(n-1)-xn|+|xn-x1|。
: ...................
--
FROM 219.142.144.*