limjunyoung

级别: 荣誉会员 一等解题奖
发贴: 879
威望: 614
金币: 1927
注册时间:2006-04-26
最后登陆:2008-10-14
|
|
倒序和<=乱序和<=正序和 a1<=a2<=a3<=a4<=a5...<=an b1<=b2<=b3<=b4<=...bn a1bn+a2bn-1+...+anb1<=a1c1+a2c2+...ancn<=a1b1+a2b2+a3b3+...anbn 其中c1,c2,c3...cn是数列bn的一种排列
Sn=c1+c2+...cn Tn=b1+b2+...bn 其中cn是数列bn的一个排列 又因为b1<=b2<=...<=bn 所以 Sk>=Tk (1<=k<=n) Sn=Tn 所以a1c1+a2c2+...ancn=a1S1+a2(S2-S1)+...an(Sn-Sn-1) =S1(a1-a2)+S2(a2-a3)+...Sn-1(an-1 -an)+anSn <=T1(a1-a2)+T2(a2-a3)+...Tn-1(an-1 -an)+anTn 因为Tk<=Sk且a1<=a2<=a3..<=an =a1T1+a2(T2-T1)+....an(Tn-Tn-1) =a1b1+a2b2+...anbn
现在a1(bn)+a2(bn-1)+....an(b1)=a1(Tn -Tn-1)+a2(Tn-1 -Tn-2)+....+an*T1 =a1Tn+Tn-1(a2-a1)+...+T1*(an-an-1) <=a1Sn+Sn-1(a2-a1)+...+S1*(an-an-1) (因为Sk>=Tk, a1<=a2<=...<=an) =a1(Sn-Sn-1)+a2(Sn-1- Sn-2)+....+an-1(S2-S1)+S1*an =a1cn+a2cn-1+....an*c1 而因为c1,c2,c3..cn本身就是一种bn的任意排列 所以c1,c2,c3....cn和cn,cn-1,cn-2...c1可以理解为是一样的 综合以上有倒序和<=乱序和<=正序和 本题中a1=3,a2=8,a3=16 c1,c2,c3是1/x,1/y,1/z 当c1>=c2>=c3也就是x<=y<=z的时候构成了倒序和,所以最小
|