当一个问题具有最优子结构时，一般我们会想到用动态规划法去解它，但是有些问题存在着更简单有效的方法，我们只要总是做出当前看来最好的选择就可以了。贪心算法所作的选择可以依赖于以往所作过的选择，但决不依赖于将来的选择，也不依赖于子问题的解，这使得算法在编码和执行的过程中都有着一定的速度优势。如果一个问题可以同时用几种方法解决，贪心算法应该是最好的选择之一。但是贪心算法并不是对所有的问题都能得到整体最优解或最理想的近似解，与搜索法等通法比较，它的适用区域相对狭窄许多，因此正确的分析、归纳、判断贪心法的应用是十分重要的。同时我们也应该知道贪心是一种方法，而不是算法，贪心法的应用需要结合其他算法。通常而言，贪心策略需要结合排序算法。【例题】删数问题【问题描述】键盘输入一个高精度的正整数N，去掉其中任意S个数字后剩下的数字按原左右次序将组成一个新的正整数。编程对给定的N和S，寻找一种方案使得剩下的数字组成的新数最小。输入数据均不需要判错。输出应包括所去掉的数字的位置和组成的新的正整数。（N不超过240位）【问题分析】对于这道试题，我们可以采用这样一种解题方式：因为要删除S个数字，我们可以一个一个的删，每一次删除的目的都是使剩下的数尽量小。那么在每一次删除时，我们应该选择那个数字？最大的数字还是最左的数字？例如5768，通过观察可以知道删除7这个数字可以使剩余的数最小。通过思考可以得出结论，每一次删除的数字应该是这个数字序列中降序子序列最左边的数字。具体可以这样操作，按高位到低位的方向搜索递减区间。若不存在递减区间，则删尾数符；否则删递减区间的首数符，这样形成了一个新的数串。然后回到串首，重复上述规则，删下一数符…以此类推，直至删除S个数符为止。例如：N=“8796542”，S=4删数过程如下：N=“8796542”{最左边的递减序列是87，删除“8”}“796542”{最左边的递减序列是96542，删除9}“76542”{最左边的递减序列是76542，删除“7”}“6542”{最左边的递减序列是6542，删除“6”}“542”【程序代码】programdelete;vari，j，k，s:integer;N:string;beginreadln(n);readln(s);whiles>0dobeginI:=1;while(i 设两个整数a，b的和为2s，且a<>b，设a＝s-1，则b＝s+1，a*b=(s-1)*(s+1)=s-1，2 如果a=s-2，则b＝s+2，a*b＝(s-2)*(s+2)＝s-4。a-b的绝对值越小，乘积的常数项越大，即乘积越大，上面的序列a1，a2，a3，a4，…，am正好满足了a-b的绝对值最小。但是还要注意两个特例就是n=3和n=4的情况，它们的分解方案分别为1，2和1，3，乘积分别为2和3。以n=10为例，先拆分为：10=2+3+4+1，最后一项为1，比4小，将其分配给前面的一项，得到10=2+3+5，所以最大的乘积为2*3*5＝30。以n=20为例，拆分为：20=2+3+4+5+6，正好是连续自然数的和，所以最大乘积为2*3*4*5*6=720。再以n=26为例，先拆分为：26=2+3+4+5+6+6，因为最后一项为6，不比最后第二项大，所以将其平均分给前面的项，优先考虑后面的项，即前面的4项各分到1，笫5项6分到2，最后是26＝3+4+5+6+8，所以最大的乘积为3*4*5*6*8＝2880。由于n可能大到10000，分解之后的各项乘积位数比较多，超过普通的数据类型的位数，所以要用到高精度运算来进行整数的乘法运算，将结果保存在数组里。5.合并果子（fruit.pasNOIP2004年提高组第2题）【问题描述】在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过n-1次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为1，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。例如有3种果子，数目依次为1，2，9。可以先将1、2堆合并，新堆数目为3，耗费体力为3。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为12，耗费体力为12。所以多多总共耗费体力=3+12=15。可以证明15为最小的体力耗费值。【输入格式】输入文件fruit.in包括两行。第一行是一个整数n(1≤n≤10000)，表示果子的种类数。第二行包含n个整数，用空格分隔，第i个整数ai(1≤ai≤20000)是第i种果子的数目。【输出格式】输出文件fruit.out包括一行，这一行只包含一个整数，也就是最小的体力耗费值。输入数据保证这个值小于231。【输入样例】【输出样例】315129【数据规模】对于30％的数据，保证有n<=1000；对于50％的数据，保证有n<=5000；对于全部的数据，保证有n<=10000。【问题分析】解决方法：模拟+排序+贪心。根据样例数据可知，果子数越小的堆，应越早合并，样例模拟合并的过程就是算法实现的过程。首先对所有的果子有小到大进行排序，合并最小果子堆，重新排序，继续合并最小果子堆，重复至完成所有果子的合并，得出最终的体力消耗值。程序代码采用的就是这种方式。但是不难发现，上面的方法需要进行n-1次的排序，比较浪费时间，改变一下思维方式，用空间换取时间的方式，另设一个数组b存放每次合并后的堆。具体方式，首先读入n堆果子的重量，并按递增顺序进行排序，得到序列a[1]…a[n]，并增加两个数a[n+1]=a[n+2]=maxinteger。设b序列初始值为空，然后从a序列和b序列的第一个元素开始寻找合并方案，并设定x和y分别为数组a和数组b的移动指针变量。这样，每次合并的方案不在乎以下三种方案：1合并两个初始堆（a[x]和a[x+1]），合并后指针变量移动为：x:=x+2；2一个初始堆a与另一个合并堆b进行合并(a[x]+b[y])，合并后指针变量移动为：x:=x+1;y：=y+1；3两个合并堆b进行合并（b[y]+b[y+1]），合并后的指针移动为:y:=y+2；不难得出，每次合并后最小体力消耗值为：Total:=total+min{a[x]+a[x+1]，a[x]+b[y]，b[x]+b[x+1]}。6.守望者的逃离（escape.pas2007年普及组第3题）【问题描述】恶魔猎手尤迫安野心勃勃，他背叛了暗夜精灵，率深藏在海底的那加企图叛变，守望者在与尤迪安的交锋中遭遇了围杀。被困在一个荒芜的大岛上。为了杀死守望者，尤迪安开始对这个荒岛施咒，这座岛很快就会沉下去，到那时岛上的所有人都会遇难：守望者的跑步速度为17m/s，以这样的速度是无法逃离荒岛的。庆幸的是守望者拥有闪烁法术，可在1s内移动60m，不过每次使用闪烁法术都会消耗魔法值10点。守望者的魔法值恢复的速度为4点/s，只有处在原地休息状态时才能恢复。现在已知守望者的魔法初值M，他所在的初始位置与岛的出口之间的距离S，岛沉没的时间T。你的任务是写一个程序帮助守望者计算如何在最短的时间内逃离荒岛，若不能逃出，则输出守望者在剩下的时间内能走的最远距离。注意:守望者跑步、闪烁或休息活动均以秒(s)为单位。且每次活动的持续时间为整数秒。距离的单位为米（m）。【输入文件】输入文件escape.in仅一行，包括空格隔开的三个非负整数M，S，T。【输出文件】输出文件escape.out包含两行:第1行为字符串“Yes”或“No”(区分大小写)，即守望者是否能逃离荒岛。第2行包含一个整数，第一行为“Yes”(区分大小写）时表示守望着逃离荒岛的最短时间第一行为“No”（区分大小写）时表示守望者能走的最远距离。【样例1输入】【样例1输出】392004No197【样例2输入】【样例2输出】3625510Yes67.排座椅（seat.pasNOIP2008年普及组第2题）【问题描述】上课的时候总有一些同学和前后左右的人交头接耳，这是令小学班主任十分头疼的一件事情。不过，班主任小雪发现了一些有趣的现象，当同学们的座次确定下来之后，只有有限的D对同学上课时会交头接耳。同学们在教室中坐成了M行N列，坐在第i行第j列的同学的位置是（i，j），为了方便同学们进出，在教室中设置了K条横向的通道，L条纵向的通道。于是，聪明的小雪想到了一个办法，或许可以减少上课时学生交头接耳的问题：她打算重新摆放桌椅，改变同学们桌椅间通道的位置，因为如果一条通道隔开了两个会交头接耳的同学，那么他们就不会交头接耳了。请你帮忙给小雪编写一个程序，给出最好的通道划分方案。在该方案下，上课时交头接耳的学生对数最少。【输入格式】输入文件的第一行，有5个用空格隔开的整数，分别是M，N，K，L，D（2<=N，M<=1000，0<=K 因篇幅问题不能全部显示，请点此查看更多更全内容