这篇文章上次修改于 410 天前，可能其部分内容已经发生变化，如有疑问可询问作者。
ACM程序设计课笔记1——贪心算法
表面理解：在对问题求解的时候每次都选择对当前情况的最优解（多次的局部最优解）。
基本步骤
- 从问题的某个初始解出发。
- 采用循环语句，当可以向求解目标前进一步时，就根据局部最优策略，得到一个部分解，缩小问题的范围或规模。
- 将所有部分解综合起来，得到问题的最终解。
贪心算法常见前提操作：排序
问题一：事件序列问题
题目描述
已知N个事件的发生时刻和结束时刻。其中的一些事件在时间上有重合。找到一个事件序列，使事件序列的事件数目最多。
题解思路
每次都取结束最早的事件。
证明（反证法）
假设所有的最长序列都不包含最早结束事件，即可证明
或者可以换个想法，每次取最早结束的事件，才能使后面选择更多的事件。
问题二：HDU 1050 Moving tables
题目描述
有400个房间，编号从1-400，偶数号房间和奇数号房间在走廊的两侧，需要再两边搬东西，默认10分钟一次，如果搬过一张，则该路径被占用，每走过一条被占用的路，就要多10分钟
解题思路
寻找最大重合度，创建一个走廊数组，每走过一个格子，就让这个格子的数值加一，再遍历一遍数组，找到最大的值，就是最大的重合度。
面对多次的数组区间修改，可以考虑到差分数组。
问题三：田忌赛马-经典版
题目描述
输入国王和田忌的马，如果赢得一分，输了丢一分，平局不得，求最高分。
解题思路
对于赛马，从故事中我们可以知道，田忌用最弱的马抵消了国王最强的马，实际上就是让自己的所有马功能最大化，赢不了的马，输给最强的，消耗对方能力，赢的了的马，就去赢。
面对贪心算法，我们可以每次考虑最强和最弱的马的情况，再根据上面的用马的法则，进行最大利用。
比较两者最快马
田忌>国王，如果田忌能赢，则赢
田忌<国王，田忌用最弱马输一局
田忌=国王，则比较最慢马
比较两者最慢马
田忌<=国王，让田忌最慢比国王最快
田忌>国王, 让田忌最慢赢国王最慢
思考题一：HDU 1800 Flying to the Mars
题目描述
给一组数，分成x组，每组都是严格递增的，求x的最小值
解题思路
同一等级士兵的最大人数，就是最小的组数
思考题二：
题目描述
键盘输入一个高精度的正整数ｎ<240位，去掉任意s（s<n）个数字后,将剩下的数字按原左右次序组成一个新的正整数。给定ｎ和ｓ，请编程输出最小的新正整数。
###题解思路
左到右遍历，一旦遇到左边数大于相邻的右边的数，则删去左边的。直到删除了s个。
思考题三：青蛙的邻居
题目描述
给你n个数字，代表了n个青蛙，每个青蛙对应的数字，代表他的邻居的数量，请问这个情况存在吗？
算法思路
实际上就是n个节点，告诉了每个节点的度，问这n个节点是否可图（如果是某个无向图的序列，则该序列可图）
度序列: 把每个点的度按照顺序排起来的序列
度序列是否可图
Havel-Hakimi定理：
升序排列，最大度数n置0，其后的n个数均减1
一旦出现负数，则不可图，若没有，重新开始一轮
