1、贪心算法简介

每一次走局部最优解，然后证明可以走到全局最优解

先猜出结论，再举出例子，如果都没有问题就严谨证明
或使用反证法

2、区间问题

区间选点
https://www.acwing.com/problem/content/907/

一般区间问题要排序，所以

(1)将每个区间按右端点从小到大排序

(2)从前往后枚举每个区间

(2.1)如果已经包含点，直接pass

(2.2)否则，选择当前区间的右端点，因为我们按右端点排序，每次放点都放在右端点覆盖区间最大

先说一种常用的证明A = B;
(1)证明A <= B (2)证明A >= B

假设我们最优解是ans，目前选了cnt个点，证明ans = cnt
可以先证明ans <= cnt , 再证明ans >= cnt;

因为ans是最优的，cnt是合法的，所以ans <= cnt

因为cnt还可以表示找到了cnt个不相交的区间，由于他们不相交，所以至少要选cnt个点，所以ans >= cnt;

这样就证明了cnt是最优解

https://www.acwing.com/activity/content/code/content/9460672/

最大不相交的区间数量
https://www.acwing.com/problem/content/910/

这道题的操作方法可以和上一题一样，也就是现在只需要证明
ans >= cnt , ans <= cnt;

由于有cnt个不相交的区间，所以cnt是合法方案 ans >= cnt

反证法证明ans <= cnt , 假设ans > cnt,那我们就需要ans个点才能覆盖所有区间，而根据之前算法可知只需要cnt个点

所以矛盾了，这样就证明了ans = cnt;

https://www.acwing.com/activity/content/code/content/9460675/

区间分组
https://www.acwing.com/problem/content/908/

1、将所有区间按左端点从小到大排序

2、从前往后处理每个区间

判断能否放到现有的某个现有的组(L[i] > Max_r)

    如果不存在则开新组，将他放进去

    如果存在，就放进去，并更新当前组的Max_r;

还是证明ans <= cnt , ans >= cnt;

因为ans是最优解，cnt是合法方案，所以ans <= cnt;

当要新加入最后区间时，前面已经有cnt - 1个区间了，如果这个区间和前面的都有重叠，那他就和前面的所有点有公共点

他们就一定不能分到一个组，就是至少需要cnt个组
所以ans >= cnt;

代码上可以用堆存储最小的Max_r来和当前区间比较
https://www.acwing.com/activity/content/code/content/9460685/

区间覆盖
https://www.acwing.com/problem/content/909/

1、将区间按左端点从小到大排序

2、从前往后枚举每个区间，在所有能覆盖st的区间中选择右端点最大的区间，然后将start更新成右端点的最大值

假设枚举到第i个区间发现两者不相同，即发现ans的第i个区间和cnt的第i个区间不是同一个区间时

cnt的第i个区间的右端点必然>=ans的第i个区间的右端点，我们把ans的第i个区间换成cnt的第i个区间之后，ans依然是一个合法解，且区间个数无改变

由此，每当出现不同的区间时都可以这样替换，这样
ans会被替换成cnt，且ans的区间个数一直不变

ans = cnt得证

https://www.acwing.com/activity/content/code/content/9460710/

3、哈夫曼树

https://www.acwing.com/problem/content/150/

Huffman树是一个经典模型，这道题目就是Huffman树得经典例题，他已经证明了此题用最小的2堆合并就可以

https://www.acwing.com/activity/content/code/content/9460784/

4、排序不等式(小学数奥)
https://www.acwing.com/problem/content/description/915/

我们发现总时间 = t1 * (n-1) + t2 * (n-2 )+ … + t(n-1) * 1;
因为第i个人打水时会有他后面的(n-i)个人等待

把n-1,n-2…看作系数，我们发现越靠前的人乘的系数越大，所以可以用排队时间从小到大来打水

使用反证法证明

设有一对ti > t[i+1] ,首先他们2个的时间只对他们2个有影响
所以可以只考虑他们2个

现在的时间：ti*(n-i) + t[i+1] * (n-i-1);
交换后的时间：t[i+1] * (n-i) + t[i] * (n - i - 1)

这2个式子相减 = ti - t[i + 1] > 0 ， 所以把他们交换更优
也就是从小到大排序

5、绝对值不等式
https://www.acwing.com/problem/content/106/

就是选择一个点x要让f(x) = |x1 - x| + |x2 - x| + … + |xn - x|
最小

从直觉上讲感觉是中点，然后来证明他

我们可以分组，分成
(|x1 - x| + |xn - x|) +(|x2 - x| + |x(n-1) - x|) + …

那如果想要其中一组数最小，那这个点就要取到他们2个的中间

然后如果有一个点同时是x1和xn的中间，同时是x2 , x(n-1)的中间… , 把货仓取到这里就是最优的，那么这个点就是中点

所以x是中点就可以了

https://www.acwing.com/activity/content/code/content/9461052/

6、推公式

https://www.acwing.com/problem/content/127/

猜结论：按wi + si升序排序

类似于小学数奥那道题的证明

先设2头相邻的a牛(上)和b牛(下) , 他们的上面的所有牛的体重和为sum , 并且满足Wa + Sa > Wb + Sb

并且容易发现他们的交换只会影响他们2个，所以不用考虑其他牛

        a               b

交换前: sum - Sa (sum+Wa) - Sb
交换后： (sum+Wb) - Sa sum - Sb;

然后把他们加上(-sum + Sa + Sb)

        a               b

交换前: Sb Sa + Wa
交换后： Wb + Sb Sa;

因为Sa + Wa > Sa + Wb , 并且Wa + Sa > Sa
所以max(交换后) < max(交换前)

而我们是要求值越小越好，所以我们发现交换后更优
也就是从小往大排序

https://www.acwing.com/activity/content/code/content/9461501/