贪心算法总结与证明
感悟
贪心算法本质上是每一步做出不劣甚至更优的选择，每一步操作都要朝着最优的方向前进。
常用证明方法
邻项交换
假设现在的集合为 \(S\)，我们把决定答案的任意两个元素交换顺序得到集合 \(T\)，计算出两个集合答案的值 \(con_S,con_T\)，写出使得 \(con_S>con_T\) 的条件，推出式子即可。
此方法用于交换后仅影响两个元素答案的时候。
直接排序
写出在最优情况下前一项与后一项的关系，然后直接写个 cmp，sort 一遍得到最优解即可。
贪心算法本质上是每一步做出不劣甚至更优的选择，每一步操作都要朝着最优的方向前进。
假设现在的集合为 \(S\)，我们把决定答案的任意两个元素交换顺序得到集合 \(T\)，计算出两个集合答案的值 \(con_S,con_T\)，写出使得 \(con_S>con_T\) 的条件，推出式子即可。
此方法用于交换后仅影响两个元素答案的时候。
写出在最优情况下前一项与后一项的关系，然后直接写个 cmp，sort 一遍得到最优解即可。