loading贪 心 算 法
近年来的信息学竞赛中，经常需要求一个问题的可行解和最优解，这就是所谓的最优化问题。贪心法是求解这类问题的一种常用算法。在众多的算法中，贪心法可以算的上是最接近人们日常思维的一种算法，他在各级各类信息学竞赛、尤其在一些数据规模很大的问题求解中发挥着越来越重要的作用。
一、什么是贪心法
贪心法是从问题的某一个初始状态出发，通过逐步构造最优解的方法向给定的目标前进，并期望通过这种方法产生出一个全局最优解的方法。做出贪心决策的依据称为贪心准则（策略），但要注意决策一旦做出，就不可再更改。贪心与递推不同的是，推进的每一步不是依据某一固定的递推式，而是做一个当时看似最佳的贪心选择，不断的将问题实例归纳为更小的相似子问题。所以，在有些最优化问题中，采用贪心法求解不能保证一定得到最优解，这时我们可以选择其他解决最优化问题的算法，如动态规划等。归纳、分析、选择贪心准则是正确解决贪心问题的关键。
二、贪心法的特点及其优缺点
贪心法主要有以下两个特点：
贪心选择性质：算法中每一步选择都是当前看似最佳的选择，这种选择依赖于已做出的选择，但不依赖于未作出的选择。
最优子结构性质：算法中每一次都取得了最优解（即局部最优解），要保证最后的结果最优，则必须满足全局最优解包含局部最优解。
利用贪心法解题的一般步骤是： 1、产生问题的一个初始解；
2、循环操作，当可以向给定的目标前进时，就根据局部最优策略，向目标前进一步； 3、得到问题的最优解（或较优解）。 贪心法的优缺点主要表现在：
优点：一个正确的贪心算法拥有很多优点，比如思维复杂度低、代码量小、运行效率高、空间复杂度低等，是信息学竞赛中的一个有力武器，受到广大同学们的青睐。
缺点：贪心法的缺点集中表现在他的“非完美性”。通常我们很难找到一个简单可行并且保证正确的贪心思路，即使我们找到一个看上去很正确的贪心思路，也需要严格的正确性证明。这往往给我们直接使用贪心算法带来了巨大的困难。
典型习题
1、删数问题
键盘输入一个高精度的正整数n（n<=240位），去掉其中任意s个数字后剩下的数字按原左右次序将组成一个正整数编程对给定的n和s，寻找一种方案，使得剩下的数字组成的新数最小。
输入： n s 输出：
最后剩下的最小数。 样例输入： 178543 4
样例输出： 13
2、一种游戏，给出自然数n，然后给出2n个自然数，例如n＝4，给出8个数： 7 9 3 6 4 2 5 3。游戏双方为A,B；假设B方有最高智力，现只允许从给出数列的两头取数；A 可以先取，取完时谁取得的数字总和大，为取胜；如果双方的和相等，仍属A胜。试问A能否找到必胜的取数算法？（1996 国际奥赛试题）
【输入】 n
2*n个自然数 【输出】
共3n+2行，其中前3n行是游戏经过。每3行分别为a方所取的数和b方所取的数，及b方取数前应给予的适当提示，让游戏者选择取哪一头的数（L/R----左端或右端）。最后2行分别为a方所取的数和与b方取得的数和。
【样例输入】 4
7 9 3 6 4 2 5 3
【样例输出】 3 L 7 9 L 3 6 L 4 2 L 5 20 19
3、noip 2002均分纸牌
有 N 堆纸牌，编号分别为 1，2，…, N。每堆上有若干张，但纸牌总数必为 N 的倍数。可以在任一堆上取若于张纸牌，然后移动。
移牌规则为：在编号为 1 堆上取的纸牌，只能移到编号为 2 的堆上；在编号为 N 的堆上取的纸牌，只能移到编号为 N-1 的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。
现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。 例如 N=4，4 堆纸牌数分别为： (1)9 (2)8 (3)17 (4)6 移动3次可达到目的：
从(3)取4张牌放到(4)（9 8 13 10） -> 从 (3) 取 3 张牌放到 (2)（9 11 10 10）-> 从 (2) 取 1 张牌放到(1)（10 10 10 10）。 输入描述
N（N 堆纸牌，1 <= N <= 100）
A1 A2 … An （N 堆纸牌，每堆纸牌初始数，l<= Ai <=10000） 输出描述
所有堆均达到相等时的最少移动次数。 样例输入 4
9 8 17 6 样例输出 3
4、 智力大冲浪
源程序名 riddle.???（pas, c, cpp） 可执行文件名 riddle.exe 输入文件名 riddle.in 输出文件名 riddle.out 【问题描述】
小伟报名参加中央电视台的智力大冲浪节目。本次挑战赛吸引了众多参赛者，主持人为了表彰大家的勇气，先奖励每个参赛者m元。先不要太高兴！因为这些钱还不一定都是你的？！接下来主持人宣布了比赛规则：
首先，比赛时间分为n个时段(n≤500)，它又给出了很多小游戏，每个小游戏都必须在规定期限ti前完成(1≤ti≤n)。如果一个游戏没能在规定期限前完成，则要从奖励费m元中扣去一部分钱wi，wi为自然数，不同的游戏扣去的钱是不一样的。当然，每个游戏本身都很简单，保证每个参赛者都能在一个时段内完成，而且都必须从整时段开始。主持人只是想考考每个参赛者如何安排组织自己做游戏的顺序。作为参赛者，小伟很想赢得冠军，当然更想赢取最多的钱！注意：比赛绝对不会让参赛者赔钱!
【输入】
输入文件riddle.in，共4行。
第1行为m，表示一开始奖励给每位参赛者的钱； 第2行为n，表示有n个小游戏；
第3行有n个数，分别表示游戏1到n的规定完成期限；