第六章-贪心算法..优秀PPT.ppt

第六章第六章 贪心算法贪心算法 若在求解一个问题时，能依据每次所得到的局部最优解，推导出全局最若在求解一个问题时，能依据每次所得到的局部最优解，推导出全局最优或最优目标。那么，我们可以依据这个策略，每次得到局部最优解答，逐优或最优目标。那么，我们可以依据这个策略，每次得到局部最优解答，逐步而推导出问题，这种策略称为贪心法。下面我们看一些简洁例题。步而推导出问题，这种策略称为贪心法。下面我们看一些简洁例题。【例【例1】在】在N行行M列的正整数矩阵中，要求从每行中选出列的正整数矩阵中，要求从每行中选出1个数，使得选出的总个数，使得选出的总共共N个数的和最大。个数的和最大。【算法分析】【算法分析】要使总和最大，则每个数要尽可能大，自然应当选每行中最大的那个数。要使总和最大，则每个数要尽可能大，自然应当选每行中最大的那个数。因此，我们设计出如下算法因此，我们设计出如下算法:读入读入N,M,矩阵数据；矩阵数据；Total:=0;For I:=1 to N do begin /对对N行进行选择行进行选择 选择第选择第I行最大的数行最大的数,记为记为K；Total:=Total+K；End；输出最大总和输出最大总和Total；从上例中我们可以看出，和递推法相仿，贪心法也是从问题的某一个初从上例中我们可以看出，和递推法相仿，贪心法也是从问题的某一个初始解动身，向给定的目标递推。但不同的是，推动的每一步不是依据某一固始解动身，向给定的目标递推。但不同的是，推动的每一步不是依据某一固定的递推式，而是做一个局部的最优选择，即贪心选择（在例中，这种贪心定的递推式，而是做一个局部的最优选择，即贪心选择（在例中，这种贪心选择表现为选择一行中的最大整数），这样，不断的将问题归纳为若干相像选择表现为选择一行中的最大整数），这样，不断的将问题归纳为若干相像的子问题，最终产生出一个全局最优解。的子问题，最终产生出一个全局最优解。特殊留意的是，局部贪心的选择是否可以得出全局最优是能否接受贪心特殊留意的是，局部贪心的选择是否可以得出全局最优是能否接受贪心法的关键所在。对于能否运用贪心策略，应从理论上予以证明。下面我们看法的关键所在。对于能否运用贪心策略，应从理论上予以证明。下面我们看看另一个问题。看另一个问题。【例【例2】部分背包问题】部分背包问题 给定一个最大载重量为给定一个最大载重量为M的卡车和的卡车和N种食品，有食盐，白糖，大米等。已知种食品，有食盐，白糖，大米等。已知第第i种食品的最多拥有种食品的最多拥有Wi公斤，其商品价值为公斤，其商品价值为Vi元元/公斤，编程确定一个装货方公斤，编程确定一个装货方案，使得装入卡车中的全部物品总价值最大。案，使得装入卡车中的全部物品总价值最大。【算法分析】【算法分析】因为每一个物品都可以分割成单位块，单位块的利益越大明显总收益越大，因为每一个物品都可以分割成单位块，单位块的利益越大明显总收益越大，所以它局部最优满足全局最优，可以用贪心法解答，方法如下：先将单位块收所以它局部最优满足全局最优，可以用贪心法解答，方法如下：先将单位块收益按从大到小进行排列，然后用循环从单位块收益最大的取起，直到不能取为益按从大到小进行排列，然后用循环从单位块收益最大的取起，直到不能取为止便得到了最优解。止便得到了最优解。因此我们特别简洁设计出如下算法：因此我们特别简洁设计出如下算法：问题初始化；问题初始化；/读入数据读入数据按按Vi从大到小将商品排序；从大到小将商品排序；I:=1;repeat if M=0 then Break;/假如卡车满载则跳出循环假如卡车满载则跳出循环 M:=M-Wi;if M=0 then 将第将第I种商品全部装入卡车种商品全部装入卡车 else 将将(M+Wi)重量的物品重量的物品I装入卡车装入卡车;I:=I+1;/选择下一种商品选择下一种商品until(M N)在解决上述问题的过程中，首先依据题设条件，找到了贪心选择标准在解决上述问题的过程中，首先依据题设条件，找到了贪心选择标准(Vi)，并依据这个标准干脆逐步去求最优解，这种解题策略被称为贪心法。，并依据这个标准干脆逐步去求最优解，这种解题策略被称为贪心法。因此，利用贪心策略解题，须要解决两个问题：因此，利用贪心策略解题，须要解决两个问题：首先，确定问题是否能用贪心策略求解；一般来说，适用于贪心策略首先，确定问题是否能用贪心策略求解；一般来说，适用于贪心策略求解的问题具有以下特点：求解的问题具有以下特点：可通过局部的贪心选择来达到问题的全局最优解。运用贪心策略解可通过局部的贪心选择来达到问题的全局最优解。运用贪心策略解题，一般来说须要一步步的进行多次的贪心选择。在经过一次贪心选择之题，一般来说须要一步步的进行多次的贪心选择。在经过一次贪心选择之后，原问题将变成一个相像的，但规模更小的问题，而后的每一步都是当后，原问题将变成一个相像的，但规模更小的问题，而后的每一步都是当前看似最佳的选择，且每一个选择都仅做一次。前看似最佳的选择，且每一个选择都仅做一次。原问题的最优解包含子问题的最优解，即问题具有最优子结构的性原问题的最优解包含子问题的最优解，即问题具有最优子结构的性质。在背包问题中，第一次选择单位重量价值最大的货物，它是第一个子质。在背包问题中，第一次选择单位重量价值最大的货物，它是第一个子问题的最优解，其次次选择剩下的货物中单位重量价值最大的货物，同样问题的最优解，其次次选择剩下的货物中单位重量价值最大的货物，同样是其次个子问题的最优解，依次类推。是其次个子问题的最优解，依次类推。其次，如何选择一个贪心标准？正确的贪心标准可以得到问题的最其次，如何选择一个贪心标准？正确的贪心标准可以得到问题的最优解，在确定接受贪心策略解决问题时，不能随意的推断贪心标准是否正优解，在确定接受贪心策略解决问题时，不能随意的推断贪心标准是否正确，尤其不要被表面上看似正确的贪心标准所迷惑。在得出贪心标准之后确，尤其不要被表面上看似正确的贪心标准所迷惑。在得出贪心标准之后应赐予严格的数学证明。应赐予严格的数学证明。下面来看看0-1背包问题。给定一个最大载重量为M的卡车和N种动物。已知第i种动物的重量为Wi，其最大价值为Vi，设定M，Wi，Vi均为整数，编程确定一个装货方案，使得装入卡车中的全部动物总价值最大。【分析】对于N种动物，要么被装，要么不装，也就是说在满足卡车载重的条件下，如何选择动物，使得动物价值最大的问题。即确定一组X1，X2，Xn，Xi0,1 f(x)=max(Xi*Vi)其中，(Xi*Wi)W 从直观上来看，我们可以依据上例一样选择那些价值大，而重量轻的动物。也就是可以按价值质量比（Vi/Wi）的大小来进行选择。可以看出，每做一次选择，都是从剩下的动物中选择那些Vi/Wi最大的，这种局部最优的选择是否能满足全局最优呢？我们来看看一个简洁的例子：设N=3，卡车最大载重量是100，三种动物A、B、C的重量分别是40，50，70，其对应的总价值分别是80、100、150。状况A：依据上述思路，三种动物的Vi/Wi分别为2,2,2.14。明显，我们首先选择动物C，得到价值150，然后随意选择A或B，由于卡车最大载重为100，因此卡车不能装载其他动物。状况B：不按上述约束条件，干脆选择A和B。可以得到价值80+100=180，卡车装载的重量为40+50=90。没有超过卡车的实际载重，因此也是一种可行解，明显，这种解比上一种解要优化。问题出现在什么地方呢？我们看看图23 从图23中明显可以看出，状况A，卡车的空载率比状况B高。也就是说，上面的分析，只考虑了货物的价值质量比，而没有考虑到卡车的运营效率，因此，局部的最优化，不能导致全局的最优化。因此，贪心不能简洁进行，而须要全面的考虑，最终得到证明。【例【例3】排队打水问题】排队打水问题 有有N个人排队到个人排队到R个水龙头去打水，他们装满水桶的时间为个水龙头去打水，他们装满水桶的时间为T1，T2，Tn为整数且各不相等，应如何支配他们的打水依次才能使他们花费的时间最少？为整数且各不相等，应如何支配他们的打水依次才能使他们花费的时间最少？【算法分析】【算法分析】由于排队时，越靠前面的计算的次数越多，明显越小的排在越前面得出的结果由于排队时，越靠前面的计算的次数越多，明显越小的排在越前面得出的结果越小（可以用数学方法简洁证明，这里就不再赘述），所以这道题可以用贪心法越小（可以用数学方法简洁证明，这里就不再赘述），所以这道题可以用贪心法解答，基本步骤：解答，基本步骤：(1)将输入的时间按从小到大排序；将输入的时间按从小到大排序；(2)将排序后的时间按依次依次放入每个水龙头的队列中；将排序后的时间按依次依次放入每个水龙头的队列中；(3)统计，输出答案。统计，输出答案。【样例输入】【样例输入】4 2 /4人打水，人打水，2个水龙头个水龙头 2 6 4 5 /每个打水时间每个打水时间参考程序主要框架如下：参考程序主要框架如下：read(n,r);Fillchar(S,Sizeof(S),0);J:=0;Min:=0;For I:=1 To N Do /用贪心法求解用贪心法求解 Begin Inc(J);If J=R+1 Then J:=1;SJ:=SJ+AI;Min:=Min+SJ;End;Writeln(Min);/输出解答输出解答【样例输出】23 /总共花费时间【例【例4】均分纸牌（】均分纸牌（NOIP2002）有有 N 堆纸牌，编号分别为堆纸牌，编号分别为 1，2，,N。每堆上有若干张，但纸牌总数必。每堆上有若干张，但纸牌总数必为为 N 的倍数。可以在任一堆上取若干张纸牌，然后移动。的倍数。可以在任一堆上取若干张纸牌，然后移动。移牌规则为：在编号为移牌规则为：在编号为 1 堆上取的纸牌，只能移到编号为堆上取的纸牌，只能移到编号为 2 的堆上；在编的堆上；在编号为号为 N 的堆上取的纸牌，只能移到编号为的堆上取的纸牌，只能移到编号为 N-1 的堆上；其他堆上取的纸牌，的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。可以移到相邻左边或右边的堆上。现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。例如例如 N=4，4 堆纸牌数分别为：堆纸牌数分别为：98176 移动移动3次可达到目的：次可达到目的：从从 取取4张牌放到张牌放到（9 8 13 10）-从从取取3张牌放到张牌放到（9 11 10 10）-从从取取1张牌放到张牌放到（10 10 10 10）。）。【输入格式】【输入格式】N（N 堆纸牌，堆纸牌，1=N=100）A1 A2 An（N 堆纸牌，每堆纸牌初始数，堆纸牌，每堆纸牌初始数，l=Ai=10000）【输出格式】【输出格式】全部堆均达到相等时的最少移动次数。全部堆均达到相等时的最少移动次数。【样例输入】【样例输入】Playcard.in 4 9 8 17 6【样例输出】【样例输出】Playcard.out 3【算法分析】【算法分析】假如你想到把每堆牌的张数减去平均张数，题目就变成移动正数，加假如你想到把每堆牌的张数减去平均张数，题目就变成移动正数，加到负数中，使大家都变成到负数中，使大家都变成0，那就意味着成功了一半！拿例题来说，平均张，那就意味着成功了一半！拿例题来说，平均张数为数为10,原张数原张数9，8，17，6，变为，变为-1，-2，7，-4，其中没有为，其中没有为0的数，我的数，我们从左边动身：要使第们从左边动身：要使第1堆的牌数堆的牌数-1变为变为0，只须将，只须将-1张牌移到它的右边张牌移到它的右边（第（第2堆）堆）-2中；结果是中；结果是-1变为变为0，-2变为变为-3，各堆牌张数变为，各堆牌张数变为0，-3，7，-4；同理：要使第；同理：要使第2堆变为堆变为0，只需将，只需将-3移到它的右边（第移到它的右边（第3堆）中去，各堆堆）中去，各堆牌张数变为牌张数变为0，0，4，-4；要使第；要使第3堆变为堆变为0，只需将第，只需将第3堆中的堆中的4移到它的移到它的右边（第右边（第4堆）中去，结果为堆）中去，结果为0，0，0，0，完成任务。每移动，完成任务。每移动1次牌，步数次牌，步数加加1。或许你要问，负数张牌怎么移，不违反题意吗？其实从第。或许你要问，负数张牌怎么移，不违反题意吗？其实从第i堆移动堆移动-m张牌到第张牌到第i+1堆，等价于从第堆，等价于从第i+1堆移动堆移动m张牌到第张牌到第i堆，步数是一样的。堆，步数是一样的。假如张数中原来就有为假如张数中原来就有为0的，怎么办呢？如的，怎么办呢？如0，-1，-5，6，还是从左，还是从左算起（从右算起也完全一样），第算起（从右算起也完全一样），第1堆是堆是0，无需移牌，余下与上相同；再，无需移牌，余下与上相同；再比如比如-1，-2，3，10，-4，-6，从左算起，第，从左算起，第1次移动的结果为次移动的结果为0，-3，3，10，-4，-6；第；第2次移动的结果为次移动的结果为0，0，0，10，-4，-6，现在第，现在第3堆已经堆已经变为变为0了，可节约了，可节约1步，余下接着。步，余下接着。参考程序主要框架如下：参考程序主要框架如下：ave:=0;step:=0;for i:=1 to n do begin read(ai);inc(ave,ai);/读入各堆牌张数，求总张数读入各堆牌张数，求总张数ave end;ave:=ave div n;/求牌的平均张数求牌的平均张数ave for i:=1 to n do ai:=ai-ave;/每堆牌的张数减去平均数每堆牌的张数减去平均数 i:=1;j:=n;while(ai=0)and(i1)do dec(j);/过滤右边的过滤右边的0 while(ij)do begin inc(ai+1,ai);/将第将第i堆牌移到第堆牌移到第i+1堆中去堆中去 ai:=0;/第第i堆牌移走后变为堆牌移走后变为0 inc(step);/移牌步数计数移牌步数计数 inc(i);/对下一堆牌进行循环操作对下一堆牌进行循环操作 while(ai=0)and(i0 do begin i：=1；/从串首起先找 while(ilength(n)and(ni1)and(n1=0)do delete(n，1，1)；输出n；/删去串首可能产生的无用零【例【例6】拦截导弹问题（】拦截导弹问题（NOIP1999）某国为了防卫敌国的导弹攻击，开发出一种导弹拦截系统，但是这种拦某国为了防卫敌国的导弹攻击，开发出一种导弹拦截系统，但是这种拦截系统有一个缺陷：虽然它的第一发炮弹能够到达随意的高度，但是以后每截系统有一个缺陷：虽然它的第一发炮弹能够到达随意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕获到敌国的导弹来袭，由一发炮弹都不能高于前一发的高度。某天，雷达捕获到敌国的导弹来袭，由于该系统还在试用阶段。所以一套系统有可能不能拦截全部的导弹。于该系统还在试用阶段。所以一套系统有可能不能拦截全部的导弹。输入导弹依次飞来的高度（雷达给出的高度不大于输入导弹依次飞来的高度（雷达给出的高度不大于30000的正整数）。的正整数）。计算要拦截全部导弹最小须要配备多少套这种导弹拦截系统。计算要拦截全部导弹最小须要配备多少套这种导弹拦截系统。【输入格式】【输入格式】n颗依次飞来的高度（颗依次飞来的高度（1n1000）.【输出格式】【输出格式】要拦截全部导弹最小配备的系统数要拦截全部导弹最小配备的系统数k。【输入样例】【输入样例】missile.in 389 207 155 300 299 170 158 65【输出样例】【输出样例】missile.out 2【输入输出样例】【输入输出样例】输入：导弹高度：输入：导弹高度：7 9 6 8 5输出：导弹拦截系统输出：导弹拦截系统K=2输入：导弹高度：输入：导弹高度：4 3 2输出：导弹拦截系统输出：导弹拦截系统K=1【算法分析】【算法分析】依据题意，被一套系统拦截的全部导弹中，最终一枚导弹的高度最低。设：依据题意，被一套系统拦截的全部导弹中，最终一枚导弹的高度最低。设：k为当前为当前配备的系统数；配备的系统数；Lk为被第为被第k套系统拦截的最终一枚导弹的高度，简称系统套系统拦截的最终一枚导弹的高度，简称系统k的最低高度（的最低高度（1kn）。）。我们首先设导弹我们首先设导弹1被系统被系统1所拦截（所拦截（k1,Lk导弹导弹1的高度）。然后依次分析导弹的高度）。然后依次分析导弹2，导弹，导弹n的高度。的高度。若导弹若导弹i的高度高于全部系统的最低高度，则断定导弹的高度高于全部系统的最低高度，则断定导弹i不能被这些系统所拦截，应增不能被这些系统所拦截，应增设一套系统来拦截导弹设一套系统来拦截导弹I(kk+1,Lk导弹导弹i的高度的高度)；若导弹；若导弹i低于某些系统的最低高度，低于某些系统的最低高度，那么导弹那么导弹i均可被这些系统所拦截。原委选择哪个系统拦截可使得配备的系统数最少，我均可被这些系统所拦截。原委选择哪个系统拦截可使得配备的系统数最少，我们不妨接受贪心策略，选择其中最低高度最小（即导弹们不妨接受贪心策略，选择其中最低高度最小（即导弹i的高度与系统最低高度最接近）的高度与系统最低高度最接近）的一套系统的一套系统p(Lp=minLj|Lj导弹导弹I的高度的高度；Lp导弹导弹i的高度的高度)（ijk）。这样可使）。这样可使得一套系统拦截的导弹数尽可能增多。得一套系统拦截的导弹数尽可能增多。依次类推，直至分析了依次类推，直至分析了n枚导弹的高度为止。此时得出的枚导弹的高度为止。此时得出的k便为应配备的最少系统数。便为应配备的最少系统数。参考程序主要框架如下：参考程序主要框架如下：k:=1;L1:=导弹导弹1的高度的高度;for i:=2 to n do begin p:=0;for j:=1 to k do if(Lj=导弹导弹i的高度的高度)then if p=0 then p:=j else if Lj从从取取3张牌放到张牌放到（9 11 10 10）-从从取取1张牌放到张牌放到（10 10 10 10）。）。【输入格式】【输入格式】N（N 堆纸牌，堆纸牌，1=N=100）A1 A2 An（N 堆纸牌，每堆纸牌初始数，堆纸牌，每堆纸牌初始数，l=Ai=10000）【输出格式】【输出格式】全部堆均达到相等时的最少移动次数。全部堆均达到相等时的最少移动次数。【样例输入】【样例输入】(Playcard.in)49 8 17 6【样例输出】【样例输出】(Playcard.out)33、拦截导弹问题（、拦截导弹问题（NOIP1999）【问题描述】【问题描述】某国为了防卫敌国的导弹攻击，开发出一种导弹拦截系统，但是这种拦截系统某国为了防卫敌国的导弹攻击，开发出一种导弹拦截系统，但是这种拦截系统有一个缺陷：虽然它的第一发炮弹能够到达随意的高度，但是以后每一发炮弹有一个缺陷：虽然它的第一发炮弹能够到达随意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕获到敌国的导弹来袭，由于该系统还都不能高于前一发的高度。某天，雷达捕获到敌国的导弹来袭，由于该系统还在试用阶段。所以一套系统有可能不能拦截全部的导弹。在试用阶段。所以一套系统有可能不能拦截全部的导弹。输入导弹依次飞来的高度（雷达给出的高度不大于输入导弹依次飞来的高度（雷达给出的高度不大于30000的正整数）。计算要的正整数）。计算要拦截全部导弹最小须要配备多少套这种导弹拦截系统。拦截全部导弹最小须要配备多少套这种导弹拦截系统。【输入格式】【输入格式】n颗依次飞来的高度（颗依次飞来的高度（1n1000）.【输出格式】【输出格式】要拦截全部导弹最小配备的系统数要拦截全部导弹最小配备的系统数k。【输入样例】【输入样例】missile.in 389 207 155 300 299 170 158 65【输出样例】【输出样例】missile.out 24、排队接水、排队接水(water.pas)【问题描述】【问题描述】有有n个人在一个水龙头前排队接水，假如每个人接水的时间为个人在一个水龙头前排队接水，假如每个人接水的时间为Ti，请编程找，请编程找出这出这n个人排队的一种依次，使得个人排队的一种依次，使得n个人的平均等待时间最小。个人的平均等待时间最小。【输入格式】【输入格式】输入文件共两行，第一行为输入文件共两行，第一行为n；其次行分别表示第；其次行分别表示第1个人到第个人到第n个人每人的个人每人的接水时间接水时间T1，T2，Tn，每个数据之间有，每个数据之间有1个空格。个空格。【输出格式】【输出格式】输出文件有两行，第一行为一种排队依次，即输出文件有两行，第一行为一种排队依次，即1到到n的一种排列；其次行为的一种排列；其次行为这种排列方案下的平均等待时间这种排列方案下的平均等待时间(输出结果精确到小数点后两位输出结果精确到小数点后两位)。【输入输出样例】【输入输出样例】water.in103 2 7 8 1 4 9 6 10 556 12 1 99 1000 234 33 55 99 812water.out532.005、最大整数（、最大整数（Noip1998连接多位数）连接多位数）【问题描述】【问题描述】设有n个正整数（n20），将它们联接成一排，组成一个最大的多位整数。例如：n=3时，3个整数13，312，343联接成的最大整数为：34331213 又如：n=4时，4个整数7，13，4，246联接成的最大整数为：7424613【输入格式】【输入格式】n n个数【输出格式】【输出格式】联接成的多位数【输入样例】【输入样例】maxnum.in313 312 343【输出样例】【输出样例】maxnum.out 343312136、纪念品分组、纪念品分组(NOIP2007)【题目描述】【题目描述】元旦快到了，校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参元旦快到了，校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参与晚会的同学所获得的纪念品价值相对均衡，他要把购来的纪念品依据价格进与晚会的同学所获得的纪念品价值相对均衡，他要把购来的纪念品依据价格进行分组，但每组最多只能包括两件纪念品，并且每组纪念品的价格之和不能超行分组，但每组最多只能包括两件纪念品，并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时间内发完全部纪念品，乐乐希望分过一个给定的整数。为了保证在尽量短的时间内发完全部纪念品，乐乐希望分组的数目最少。组的数目最少。你的任务是写一个程序，找出全部分组方案中分组数最少的一种，输出最你的任务是写一个程序，找出全部分组方案中分组数最少的一种，输出最少的分组数目。少的分组数目。【输入格式】【输入格式】输入文件输入文件group.in包含包含n+2行：行：第第1行包括一个整数行包括一个整数w，为每组纪念品价格之和的上限。，为每组纪念品价格之和的上限。第第2行为一个整数行为一个整数n，表示购来的纪念品的总件数。，表示购来的纪念品的总件数。第第3n+2行每行包含一个正整数行每行包含一个正整数pi(5=pi=w)，表示所对应纪念品的价，表示所对应纪念品的价格。格。【输出格式】【输出格式】输出文件输出文件group.out仅一行，包含一个整数，即最少的分组数目。仅一行，包含一个整数，即最少的分组数目。【输入输出样例】【输入输出样例】【限制】【限制】50%的数据满足：的数据满足：1=n=15 100%的数据满足：的数据满足：1=n=30000,80=w=200group.ingroup.in1009902020305060708090group.outgroup.out67、合并果子、合并果子(Noip2004)【问题描述】【问题描述】在一个果园里，多多已经将全部的果子打了下来，而且按果子的不同种类分在一个果园里，多多已经将全部的果子打了下来，而且按果子的不同种类分成了不同的堆。多多确定把全部的果子合成一堆。成了不同的堆。多多确定把全部的果子合成一堆。每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，全部的果子经过重量之和。可以看出，全部的果子经过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。【样例输入】【样例输入】31 2 9【样例输出】【样例输出】15【数据规模】【数据规模】对于30%的数据，保证有n=1000；对于50%的数据，保证有n=5000；对于全部的数据，保证有n=10000。8、美元汇率（、美元汇率（DOLLARS.PAS）【问题描述】【问题描述】在以后的若干天里戴维将学习美元与德国马克的汇率。编写程序帮助戴在以后的若干天里戴维将学习美元与德国马克的汇率。编写程序帮助戴维何时应买或卖马克或美元，使他从维何时应买或卖马克或美元，使他从100美元起先，最终能获得最高可能的价美元起先，最终能获得最高可能的价值。值。【输入格式】【输入格式】输入文件的第一行是一个自然数输入文件的第一行是一个自然数N，1N100，表示戴维学习汇率的天，表示戴维学习汇率的天数。数。接下来的接下来的N行中每行是一个自然数行中每行是一个自然数A，1A1000。第。第i+1行的行的A表示预先知道表示预先知道的第的第i+1天的平均汇率，在这一天中，戴维既能用天的平均汇率，在这一天中，戴维既能用100美元买美元买A马克也能用马克也能用A马马克购买克购买100美元。美元。【输出格式】【输出格式】输出文件的第一行也是唯一的一行应输出要求的钱数输出文件的第一行也是唯一的一行应输出要求的钱数(单位为美元，保留单位为美元，保留两位小数两位小数)。留意：考虑到实数算术运算中进位的误差，结果在正确结果留意：考虑到实数算术运算中进位的误差，结果在正确结果0.05美元范美元范围内的被认为是正确的，戴维必需在最终一天结束之前将他的钱都换成美元。围内的被认为是正确的，戴维必需在最终一天结束之前将他的钱都换成美元。【输入样例】【输入样例】DOLLARS.IN5400300500300250【输出样例】【输出样例】DOLLARS.OUT266.66样例说明样例说明(无需输出无需输出)Day 1.changing 100.0000 美元美元=400.0000 马克马克Day 2.changing 400.0000 马克马克=133.3333 美元美元Day 3.changing 133.3333 美元美元=666.6666 马克马克Day 5.changing 666.6666 马克马克=266.6666 美元美元9、零件分组（、零件分组（stick.pas）【问题描述】【问题描述】某工厂生产一批棍状零件，每个零件都有确定的长度（某工厂生产一批棍状零件，每个零件都有确定的长度（Li）和重量）和重量（Wi）。现在为了加工须要，要将它们分成若干组，使每一组的零件都）。现在为了加工须要，要将它们分成若干组，使每一组的零件都能排成一个长度和重量都不下降（若能排成一个长度和重量都不下降（若ij，则，则Li=Lj，Wi=Wj）的序列。）的序列。请问至少要分成几组请问至少要分成几组?【输入格式】【输入格式】第一行为一个整数第一行为一个整数N（N=1000），表示零件的个数。其次行有），表示零件的个数。其次行有N对对正整数，每对正整数表示这些零件的长度和重量，长度和重量均不超过正整数，每对正整数表示这些零件的长度和重量，长度和重量均不超过10000。【输出格式】【输出格式】仅一行，即最少分成的组数。仅一行，即最少分成的组数。【输入样例】【输入样例】STICK.IN58 4 3 8 2 3 9 7 3 5【输出样例】【输出样例】STICK.OUT2