排序不等式

排序不等式(排序原理)

推荐B站大佬的视频讲解: https://www.bilibili.com/video/BV1hE411x7f7?from=search&seid=6488010905221350651

设数组 $a$a, $b$b和 $c$c

a[ ]为a1​<=a2​<=a3​....<=an​  a[ ]数组递增

b[ ]为b1​<=b2​<=b3​....<=bn​  b[ ]数组递增

$c\left[\right]为b\left[\right]数组的一个排列$c[ ]为b[ ]数组的一个排列

记

$S_1=a_1\ast b_n+a_2\ast b_{n-1}+a_3\ast b_{n-2}+...+a_n\ast b_1$S1​=a1​∗bn​+a2​∗bn−1​+a3​∗bn−2​+...+an​∗b1​ (反序和)

$S=a_1\ast c_1+a_2\ast c_2+a_3\ast c_3+.....a_n\ast c_n$S=a1​∗c1​+a2​∗c2​+a3​∗c3​+.....an​∗cn​ (乱序和)

$S_2=a_1\ast b_1+a_2\ast b_2+a_3\ast b_3+......+a_n\ast b_n$S2​=a1​∗b1​+a2​∗b2​+a3​∗b3​+......+an​∗bn​ (顺序和)

则 S1​<=S<=S2

即 : 反序和 <= 乱序和 <= 顺序和

可用排序原理证明

• $a^2+b^2>=2ab$a2+b2>=2ab (均值不等式)
• $a^2+b^2+c^2>=ab+bc+ca$a2+b2+c2>=ab+bc+ca

打水问题, $n$n个人排队打水,第 $i$i个人要等 $a\left[i\right]$a[i]的单位时间,如何才能使得所有人的等待时间最小
很明显让最快的人先打水更优