逆序对--P1966 火柴排队

*题意:两个数组$a$和$b$,使$\sum_{i=1}^n {(a_i-b_i)}^2$ 最小

*思路:对于上述的完全平方公式,展开后变成$\sum_{i=1}^n {a_i}^2+{b_i}^2-2a_ib_i$,其中前两项为定值,我们继续变化$\sum_{i=1}^n {a_i}^2+{b_i}^2$-2$\sum_{i=1}^n a_ib_i$

只要令$\sum_{i=1}^n a_ib_i$越大越好,由此我们引入一个结论顺序之乘>=乱序之乘

*证明:设有序数列$x$,$y$,即有$x_1y_1+x_2y_2$>$x_1y_2+x_2y_1$

变形一下可得$x_1y_1-x_2y_1$>$x_1y_2-x_2y_2$ $\to$ $y_1(x_1-x_2)$>$y_2(x_1-x_2)$,因为$y_1$>$y_2$,第一个式子成立

由1及2,再到$n$,得出结论顺序之乘>=乱序之乘

 

上一篇:如何理解三极管 基极与发射极交流等电压


下一篇:三极管~2.电路分析