贪心算法

---

---

总是做出【当前看来】最好的选择：不考虑全局最优解，只考虑当前步骤最优解。

###1.事件序列问题：
eg:2037
已知N个事件的发生时刻和结束时刻，一些在时间上没有重叠的事件看作一个事件序列。尝试找出最长的事件序列。
“最长”的定义是序列内事件数量最多，不是指时间最长~~(妈的智障)~~
思路：
1.持续寻找最短的事件
（这个事件可能打断两个连续的长事件）
2.持续寻找最早结束的事件。
命题 至少存在一个最长的事件序列，包含最早结束的事件
证明 (反证法) 假设所有最长事件序列都不包含最早结束的事件，那么如果把最先的时间替换为最早结束的事件，新的序列与原序列等长，是最长事件序列，但是包含了最早结束的事件，因此出现矛盾。

###2.搬桌子问题
eg:1050
最少需要搬多长时间与最高重叠度有关。
思路：
将走廊房间号定义为数组，每有一个桌子经过，则重叠度（数组值）+1，从而得出最高重叠度。

###3.田忌赛马问题
合理搭配对战顺序，求最好的比赛结果。
####3.1 经典版：无平局
思路：从自己最好的马开始，每次选择劣于自己的马的速度最少的对方马。
####3.2 升级版：有平局
eg:
King: 200 180 160
Tian: 180 155 150
先排序，
找到田忌和国王的最好的马，如果赢则比赛，如果不能赢，（既然最好的也比不过，那么就）用最差的比赛。
然后把已选的去掉接着比较。
出现平局时，看自己最差的，如果比不过对面最差的，则用自己的最差的马打破平局。如果两边最差的是平局，则用己方最差比赛对面最好的。
###4.变化的贪心问题
####1.
eg:1800

####2.
####3.
eg:n个正整数，将它们连成一排组成一个整数，求其中最大的整数。
如13 312 343
思路：先比较第一位，最大的放最前面，若第一位相同，则把其中第二位大的放前面……
特例： 12 121和12 123；
43 432和43 434
思路:把两种可能作为字符串接起来，然后进行字符串比较。
注意 要考虑到所有情况（如特例中的所有情况)

####4.青蛙邻居问题
若两湖泊有水道连接则认为在该湖泊内的青蛙有邻居,每个湖泊只有一只青蛙。
给出湖泊数和每个青蛙的邻居数，求这个给定的组合是否存在。

问题简化：
(数据:7湖泊，4 3 1 5 4 2 1)
7个节点，每个节点与相邻节点有连线（不交叉）
连线数称为“度”
=>可图性判定：
首先把度排序
先满足“度”最高的项，（此时剩余项-1）然后从高到低满足
如果某次最大项的邻居数比剩余项数少，则先减剩余项中较大的。
每次做完后重新排序
eg:
7 4 3 3 3 3 2 1
减> 3 2 2 2 2 1 0
减> (1 1 1 2 1 0)
排序> 2 1 1 1 1 0
…
…

如果其中有项出现负数，说明不可图。

####5.币值问题
货币系统有一角、五分、一分，求最小找币数，能否用贪心求解？
A：如果大的币值是小币值的倍数，则可用。

###5.排序问题
unfinished.