区间选点

这里使用夹逼定理进行证明，后面的最大不相交区间和区间分组都是用的这个方式
Ans<=cnt证明：
因为Ans表示的是最优解，即所用点数最少；而cnt只是求出了一个合法解，合法解的点数必然小于等于最优解

Ams>=cnt证明：
根据y总当时的贪心策略，当前区间不包含点时我们会选择它的右端点作为最终解中的一个点，因为选择的是右端点且区间是按右端点从小到大排序的，所以当前不包含点的区间与上一个选了右端点的区间，两者之间必然不存在交集；由此，这cnt个选择了右端点作为最终解的区间彼此之间必然不存在交集，即所有区间中至少存在cnt个彼此不相交的区间；如此，要想让选出的点覆盖所有区间，至少需要选cnt个点，即任何一个方案都至少包含cnt个点，最优解也不例外；Ans>=cnt得证

最大不相交区间

Ans>=cnt证明：
这道题的结论是我们先按区间选点那道题的贪心策略，选出至少需要cnt个点才能覆盖掉所有区间，而当时在证明cnt是最优解的时候，我们通过分析得出“这cnt个选择了右端点作为最终解的区间彼此之间必然不存在交集”，即我们选出了cnt个不相交的区间，所以cnt同时也是最大不相交区间这道题的一个合法解。
由于cnt是一个合法解，所以必然满足Ans>=cnt

Ans<=cnt的证明：
这里使用的是反证法，即假设Ans>cnt，如果得出了与已知结论矛盾的结论，则可推出原命题不成立（命题逻辑里的拒取式）。而我们现在已有的已知结论就是，至少需要使用cnt个点才可以覆盖掉所有区间，而现在我们可以找到有Ans个区间彼此之间是不相交的，此时我们想要覆盖掉所有区间至少需要Ans个点，而Ans>cnt，这于我们的已知结论是矛盾的，所以原命题Ans>cnt不成立，即Ans<=cnt

区间分组

Ans<=cnt证明：
因为Ans是最优解，而我们根据贪心策略得出来的cnt肯定是一个合法解，所以必然有Ans<=cnt的

Ans>=cnt证明：
根据我们的贪心策略，对于第一个进入第cnt个分组的区间（我们把它命名为X区间），它和前面的cnt-1个分组必然存在交集（否则就不会产生第cnt组了），即我们必然能够在前面的cnt-1个分组的每一组中找到一个和它相交的区间，如此，我们便可以找到cnt-1个区间和X区间相交，即至少有cnt个区间彼此是相交的，如果要进行分组，这cnt个区间必然处于不同组，即至少需要分成cnt组，所以任何一种分组方案得到的结果都必然>=cnt，最优解与不例外，所以Ans>=cnt得证

区间覆盖

这道题的贪心策略y总在证明的时候讲得有点乱，然后证明的方式和前面三题的证明方式都不同，具体如下：
假设最优解有Ans个区间，用贪心策略得出的解是cnt个区间。我们依次枚举这ans个区间和cnt个区间，假设枚举到第i个区间发现两者不相同，即发现ans的第i个区间和cnt的第i个区间不是同一个区间时（此时ans的第i-1个区间和cnt的第i-1个区间相同）根据我们的贪心策略，cnt的第i个区间的右端点必然>=ans的第i个区间的右端点，如此我们把ans的第i个区间换成cnt的第i个区间之后，ans依然是一个合法解，并且此时ans中的区间个数没有发生改变；由此，每当出现不相同的区间时，我们都可以采用这种替换，最终最优解的每个区间在经过上述替换后，会等于我们用贪心策略得出的解的每个区间，即这两个解的区间个数是相同的，Ans=cnt得证

合并果子

这道题的证明比较绕，然后我感觉让我来说也很难说清楚，感兴趣的同学可以去算法导论上看严格的证明（第三版248页）
然后个人认为这道题的重点应该不是放在证明，而是如何用哈夫曼算法解决这道题（毕竟哈夫曼算法算是比较常见的一种贪心算法，正确性是百分百的，只要我们能想到使用它，正确性的证明其实已经不需要了，不像其他几道题的贪心策略，刚想到的时候正确与否还是未知的，需要我们自己去证明）

排队打水

这里使用反证法，后面的耍杂技的牛用的也是反证法证明的
这里假设使用贪心策略得出的打水顺序不是最优解，即最优解中存在逆序对（就是存在打水时间久的排在打水时间少的人前面）是正确的，如果我们能够通过这个结论得出错误的结论，则说明原结论不成立。

而我们现在所知道的正确的结论是最优解每个人的排队打水等待的总时间一定是最少的。

当最优解中存在逆序对时，我们把打水时间少的人换到打水时间长的人前面时（即变成顺序），最优解的排队打水等待的总时间是变少的（这步证明看下图），这与我们的已知结论“最优解的每个人的排队打水等待的总时间一定是最少的”相矛盾，即我们得出了一个错误的结论，由此原假设“使用贪心策略得出的打水顺序不是最优解是正确的”不成立，即用贪心得出的解是最优解

货仓选址

这道题的贪心策略是先对给出的每个点进行排序，然后选择中点作为货仓位置（奇数个点是中间的点，偶数个点根据C++下取整应该是中间两个点中较小的那个点），然后证明看下图，图中的已知结论可以自己去百度查，然后从最终结论可以看出，不仅选中点可以得到最优解，其实选在[x2,x3]中的任意一点都可以，只是为了计算方便我们选择中点而已

耍杂技的牛

这道题的贪心策略是按照牛的体重加强壮程度从小到大排序，小的在上，大的在下（这样也符合常理，小的在下就要被压死了），然后证明是使用反证法，思路和排队打水那题差不多，假设按照贪心策略得出的解不是最优解，即最优解中存在逆序（存在体重加强壮程度大的牛，排在体重加强壮程度小的牛上面），如果我们能够发现这个所谓的“存在逆序的最优解”的风险值的最大值还可以继续变小（这步证明看下图），则说明原假设与已知结论“最优解的风险值的最大值是所有方案中最小的”矛盾，如此便可得出原假设不成立，即贪心策略得出的解是最优解。