文档介绍：贪心算法
    一、问题举例:谷仓修补[1999 USACO Spring Open]
    有一长列畜栏,其中的一些需要用木板覆盖。你可以用最多N个(1<=N<=50)木板,其中的每一个都可以覆盖任意数量的连续畜栏。覆盖全部需要覆盖的畜栏,但是使被覆盖的畜栏尽量少。
    思想:
    
    在贪心算法背后隐藏的基本思想是从小的方案推广到大的解决方法。然而与其他方法不同的是,贪心算法只需随着过程的进行保持现下的最好方案。因此,对于这个例题,如果需要找到N=5时的最优方案,应该寻找N=4时的最优解,然后加以改变得到N=5的解法。至于N=4时的其它解法,可以不予考虑。
    贪心算法快速,而且仅需要很小的额外内存消耗。但是很不幸地,它往往是不正确的。然而当他们的确是正确的时候,便可以很轻易地贯彻执行并拥有足够快的速度。
    问题:
    
    贪心算法有两个基本的问题。
    如何建立:
    怎样从一个规模较小的解推出规模较大的解呢?拿这个例题来说,从四个木板变化到五个木板的最明显的途径是将一个木板移去一部分而拆成两个。你应该选择移除最大的只覆盖了不需要覆盖的部分。
为了移除这样的部分,选择跨越了这部分的一块木板将它拆成两部分,一块覆盖这些畜栏之前的部分,另一块覆盖这些畜栏之后的部分。
    解法确实正确?
    对于程序员来说,真正的挑战在于贪心算法不一定总是有效这个事实。即使它对于特定输入,随机输入,乃至一切你能想到的情况都是正确的,但是如果如果有一种情况它不能正确地工作,至少一个(或者更多)的裁判测试就会是这种类型。
    对于这个例题,为了确保贪心算法确实是有效的应该做如下的考虑:
    假设答案并没有包含贪心算法移除的大型缺口,而是包含了一个小一些的缺口,通过将较小缺口两端的木板合并并炸开跨越了更大缺口的木板所得到的答案,使用了和原先一样多的木板,但是覆盖的畜栏更少一些。这个新的方案更好一些,所以之前的假设是错误的,我们总是应该选择移除最大的缺口。
    如果答案没有包含这个特定的缺口而是包含了一个正好和它一样大的缺口,通过同样做法所产生出的答案在覆盖的畜栏和使用的木板数上均与原来相同。新方法与原方法效果相同而不是更加出色,所以我们选择哪一个都是可以的。
    因此,确实存在着一个包含了大缺口的最佳答案,每步都是如此,每前进一步所得到的最优方案都是上一步的超集。因此最后的方案是最优的。
    结论:
    如果一个贪心解决方案存在,就使用它。它易于编码,易于调试,运行快速,消耗内存少,是竞赛中的很好的算法。这其中唯一缺少的成分是正确性。如果贪心算法找到了正确的答案,坚决地使用它,但是永远不要以为贪心算法对全部的问题都有效。
   
二、问题举例:对一个有三个值的序列排序[IOI 1996]
    
    有一个包含三个值(1,2,3)的序列,其长度不超过1000。寻找一个方案使用最小次数的交换将序列排序。
    排序后的序列被分为三个部分,为1的部分,为2的部分和为3的部分。贪心算法将尽可能多的1部分中的2与2部分中的1交换,将尽可能多的1部分中的3与3部分中的1交换,将尽可能多的2部分中的3与3部分中的2交换。一旦这种情况不再存在,剩余的