本题排序规则证明

证明：排序不等式

假设对于两辆车

i,j

，

i

在

p_1

，

j

在

p_2

，如果把

i

移到

j

更优，就要求原来的总代价大于交换后的总代价，即：

2 \times a[i] \times p_1 + 2 \times b[i] \times (x - p_1) + 2 \times a[j] \times p_2 + 2 \times b[j] \times (x - p_2) > 2 \times a[i] \times p_2 + 2 \times b[i] \times (x - p_2) + 2 \times a[j] \times p_1 + 2 \times b[j] \times (x - p_1)

\Rightarrow a[i] \times p_1 - b[i] \times p_1 + a[j] \times p_2 - b[j] \times p_2 > a[i] \times p_2 - b[i] \times p_2 + a[j] \times p_1 - b[j] \times p_1

\Rightarrow a[i] \times (p_1 - p_2) + b[i] \times (p_2 - p_1) > a[j] \times (p_1 - p_2) + b[j] \times (p_2 - p_1)

\Rightarrow (a[i] - b[i])(p_1 - p_2) > (a[j] - b[j])(p_1 - p_2)

\Rightarrow a[i] - b[i] > a[j] - b[j]

讨论操作