贪心常用证明方法：
1. 反证法 调整法
2. 数学归纳法
3. 证明两个方向 ans >= cnt && ans <= cnt

排队不等式

排队打水：
有 n 个人排队到 1 个水龙头处打水，第 i 个人装满水桶所需的时间是 ti，请问如何安排他们的打水顺序才能使所有人的等待时间之和最小？

算法：
    小学奥数
    推公式：总时间 = t1 * (n - 1) + t2*(n - 2) + ... 
    要使总时间最小，则短的放在前面即可

    按照从小到大的顺序排队，总时间最小

证明：
    调整法：假设最优解不是按照从小到大排好序的，那么必然存在两个相邻元素，前一个必后一个大(t[i] > t[i+1])，假如交换这两个位置，交换后ti+1 * (n - i) + ti * (n - i - 1), 交换前ti * (n - i) + ti+1 * (n - i - 1)；两式相减发现交换后比交换前时间更短，得到ti - ti+1 > 0，故与假设矛盾；所以必从小到大排序的才是最优解

绝对值不等式
货仓选址：
在一条数轴上有 N 家商店，它们的坐标分别为 A1∼AN。
现在需要在数轴上建立一家货仓，每天清晨，从货仓到每家商店都要运送一车商品。
为了提高效率，求把货仓建在何处，可以使得货仓到每家商店的距离之和最小。

高中数学爷青回: |a - x| + |b - x|最小值为|a - b|

推公式得距离之和 = | x1 - x | + |x2 - x| + ... + |xn - x|， x为货仓地址
分组，第一个和最后一个。。。两两分组
(| x1 - x | + + |xn - x|) + (|x2 - x| + |xn-1 - x} + ...

>= xn - x1 + xn-1 - x2 + ...
等号成立需要x在所有数得中位数时等号成立
所以货舱在中点距离最小

推公式：贪心问题要严谨推公式，不能纯猜
耍杂技的牛

农民约翰的 N 头奶牛（编号为 1..N）计划逃跑并加入马戏团，为此它们决定练习表演杂技。

奶牛们不是非常有创意，只提出了一个杂技表演：

叠罗汉，表演时，奶牛们站在彼此的身上，形成一个高高的垂直堆叠。

奶牛们正在试图找到自己在这个堆叠中应该所处的位置顺序。

这 N 头奶牛中的每一头都有着自己的重量 Wi 以及自己的强壮程度 Si。、

一头牛支撑不住的可能性取决于它头上所有牛的总重量（不包括它自己）减去它的身体强壮程度的值，现在称该数值为风险值，风险值越大，这只牛撑不住的可能性越高。

您的任务是确定奶牛的排序，使得所有奶牛的风险值中的最大值尽可能的小。


算法
    按照wi + si从小到大的顺序排，最大的危险系数一定是最小的

证明：
    贪心算法得到的答案是一种方案一定>= 最优解(最小值)
    如果不满足贪心算法顺序，则一定有wi + si > wi+1 + si+1再推推公式可得交换位置后答案更佳，所以不存在逆序对