[TOC]
中位数贪心
一个简单的问题：我们有一个数组a，我们要找一个数x，使得数组a中的每一个数到x的绝对距离之和最小，那么这个数是多少？
定理: 将 $a$ 的所有元素变为 $a$ 的中位数是最优的。 证明: 设 $a$ 的长度为 $n$ ，设要将所有 $a[i]$ 变为 $x$ 。假设 $a$ 已经从小到大排序。首先，如果 $x$ 取在区间 $[a[0], a[n-1]]$ 之外，那么 $x$ 向区间方向移动可以使距离和变小; 同时，如果 $x$ 取在区间 $[a[0], a[n-1]]$ 之内，无论如何移动 $x$ ，它到 $a[0]$ 和 $a[n-1]$ 的距离和都是一个定值 $a[n-1]-a[0]$ ，那么去掉 $a[0]$ 和 $a[n-1]$ 这两个最左最右的数，问题规模缩小。不断缩小问题规模，如果最后剩下 1 个数，那么 $x$ 就取它; 如果最后剩下 2 个数，那么 $x$ 取这两个数之间的任意值都可以（包括这两个数）。因此 $x$ 可以取 $a[n / 2]$ 。
Leetcode 题单
462. 最小操作次数使数组元素相等 II
2033. 获取单值网格的最小操作数 1672
2448. 使数组相等的最小开销 2005
2607. 使子数组元素和相等 2071
1703. 得到连续 K 个 1 的最少相邻交换次数 2467
