今天眼睛抱恙了，看的非常累，不是平常的那种疲惫，而是略带痛的感觉。但是问题不大。

看了算法书上最优服务次序问题，记得当时算法课上，沈云付说过这是一个结论不等式，具体名字忘了，

对于a1…an, b1…bn， 则sum(i=1->n)ai*bi 里面一个递增，一个递减排列是所有排列里面最小的。

具体证明如下：假设当前已经是最优排列(a1b2…bn)，若交换b1 b2

则(a2b1+a1b2)-(a1b1+a2b2)=(b1-b2)(a2-a1)>0,因此交换之后都是变大的。记得一次在食堂炒肉大神口述了一下这个过程
重要的是，这个结论不仅用于正数，而且用于负数

用于ECNU一道向量点积最小题，还有这道最优服务次序，本质是min((n-1)a1+….an-1), 因此a[]递增排列是最小的。

Posted by richard爱闹 - 4月 3 2015
如需转载，请注明： 本文来自 Richard