相关结论：

在满足花费最小化的前提下，一定存在一种构造B的方案，使得B中的每个数都是A序列中的数

证明：数学归纳法

• 以单调不降为例

• 当 $n=1$ 时，结论显然成立

• 假设 $n=k-1$ 时结论成立，则当 $n=k$ 时：

  • 若 $A_k \ge B_{k-1}$ 则可以不动 $A_k$ ,单调性以及正确性显然

  • 若 $A_k <B_{k-1}$ 则可以发现只能在这种为维护单调性而调整的方式中寻找最优解：

    • 令 $i \in [1,k-1]$ 让 $i$ 之后的所有元素(包括 $A_k$ )全部变为 $x$ ，并且满足 $x\ge B_i$

    • 若 $i=k-1$ 则结论显然成立

    • 若 $i<k-1$ 证明如下：

      • 此时的总代价为 $cost_i+\sum\limits_{j=i+1}^k|a_j-x|$

      • 对于固定的 $i$ 而言，左半部分是固定的，右半部分是一个绝对值函数，且是一个凸函数，其取最小值时， $x$ 为 $[i+1,k]$ 之间的中位数，也就是说，一定存在一个 $a_p$ , 使得 $x=a_p$ 那么当然就有 $B_k=x=a_p \in A$

      • 又因为在这种情况下只有这样调整才能满足单调性，所以最优解的对应方案一定在这种调整方式中，即一定存在一个固定的 $i$ 能够让这种情况下的代价最小，而对于任意一个 $i$ 都满足上述性质，所以结论成立

        ​ $\mathcal{Q.E.D}$