排序不等式与切比雪夫不等式

0x01.排序不等式

已知$a_1\le a_2\le \cdots \le a_n,b_1\le b_2\le \cdots \le b_n,i_1,i_2,\cdots,i_n$为$1,2,\cdots,n$的一个排列，则

$$a_1b_1+\cdots+a_nb_n\ge a_1b_{i_1}+\cdots+a_nb_{i_n}\ge a_1b_n+\cdots+a_nb_1$$

其中$a_1b_1+\cdots+a_nb_n$为顺序和，$a_1b_n+\cdots+a_nb_1$为逆序和

0x02.切比雪夫不等式

已知$a_1\le a_2\le \cdots \le a_n,b_1\le b_2\le \cdots \le b_n$，则

$$a_1b_1+\cdots+a_nb_n\ge \cfrac{1}{n}(a_1+a_2+\cdots+a_n)(b_1+b_2+\cdots+b_n)\ge a_1b_n+\cdots+a_nb_1$$

0x03.排序不等式的注释

若$f(x)$单调递增，$g(x)$单调递增或$f(x)$单调递减，$g(x)$单调递减，则$f(x_1)g(x_1)+\cdots+f(x_n)g(x_n)$为顺序和

若$f(x)$单调递增，$g(x)$单调递减或$f(x)$单调递减，$g(x)$单调递增，则$f(x_1)g(x_1)+\cdots+f(x_n)g(x_n)$为逆序和