贪心法例题

3.1 排队接水

源程序名 water.???（pas, c, cpp） 可执行文件名 water.exe 输入文件名 water.in 输出文件名 water.out 【问题描述】 有n个人在一个水龙头前排队接水，假如每个人接水的时间为Ti，请编程找出这n个人排队的一种顺序，使得n个人的平均等待时间最小。 【输入】

输入文件共两行，第一行为n；第二行分别表示第1个人到第n个人每人的接水时间T1，T2，…，Tn，每个数据之间有1个空格。 【输出】

输出文件有两行，第一行为一种排队顺序，即1到n的一种排列；第二行为这种排列方案下的平均等待时间(输出结果精确到小数点后两位)。 【样例】 water.in water.out 10 3 2 7 8 1 4 9 6 10 5 56 12 1 99 1000 234 33 55 99 812 291.90 【算法分析】 平均等待时间是每个人的等待时间之和再除以n，因为n是一个常数，所以等待时间之和最小，也就是平均等待时间最小。假设是按照1~n的自然顺序排列的，则这个问题就是求以下公式的最小值：

itotalT1(T1T2)(T1T2T3)(T1T2Tn)Tj

i1j1n 如果用穷举的方法求解，就需要我们产生n个人的所有不同排列，然后计算每种排列所需要等待的时

间之和，再“打擂台”得到最小值，但这种方法需要进行n!次求和以及判断，时间复杂度很差！ 其实，我们认真研究一下上面的公式，发现可以改写成如下形式：

totalnT1(n1)T2(n2)T32Tn1Tn(n1i)Ti

i1n

这个公式何时取最小值呢？对于任意一种排列k1, k2, k3, …, kn，当Tk1≤Tk2≤Tk3≤…≤Tkn时，total

取到最小值。如何证明呢？方法如下：

因为totalnTk1(n1)Tk2(ni1)Tki(nj1)TkjTkn

假设i1

totaltotal2total1

(ni1)Tkj(nj1)Tki((ni1)Tki(nj1)Tkj)(ni1)(TkjTki)(nj1)(TkjTki)(ji)(TkjTki)

我们发现上述△total恒大于0，所以也说明了任何次序的改变，都会导致等待时间的增加。从而证明了我们的设想。 既然如此，我们就得到了一种最有贪心策略：把接水时间少的人尽可能排在前面。这样一样，问题的本质就变成：把n个等待时间按非递减顺序排列，输出这种排列，并求出这种排列下的平均等待时间。

3.2 智力大冲浪

源程序名 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的规定完成期限； 第4行有n个数，分别表示游戏1到n不能在规定期限前完成的扣款数。 【输出】 输出文件riddle.out，仅1行。表示小伟能赢取最多的钱。 【样例】 riddle.in riddle.out 10000 9950 7 4 2 4 3 1 4 6 70 60 50 40 30 20 10 【算法分析】

因为不同的小游戏不能准时完成时具有不同的扣款权数，而且是最优解问题，所以本题很容易就想到了贪心法。贪心的主要思想是要让扣款数值大的尽量准时完成。这样我们就先把这些任务按照扣款的数目进行排序，把大的排在前面，先进行放置。假如罚款最多的一个任务的完成期限是k，我们应该把它安排在哪个时段完成呢?应该放在第k个时段，因为放在1～k任意一个位置，效果都是一样的。一旦出现一个不可能在规定时限前完成的任务，则把其扔到最大的一个空时间段，这样必然是最优的，因为不能完成的任务，在任意一个时间段中罚款数目都是一样的，具体实现请看下面的参考程序1。

2

本题也可以有另外一种贪心算法，即先把所有的数据按照结束时间的先后排序，然后从前向后扫描。 当扫描到第n个时段，发现里面所分配的任务的结束时间等于n-1，那么就说明在前面这些任务中必须舍弃一个，于是再扫描第1～n这n个时段，挑出一个最小的去掉并累加扣款值，然后再去调整排列顺序，让后面的元素填补前面的空缺，具体实现请看下面的参考程序2。

3.3 取火柴游戏

源程序名 match.???（pas, c, cpp） 可执行文件名 match.exe 输入文件名 match.in 输出文件名 match.out 【问题描述】 输入k及k个整数n1，n2，…，nk，表示有k堆火柴棒，第i堆火柴棒的根数为ni；接着便是你和计算机取火柴棒的对弈游戏。取的规则如下：每次可以从一堆中取走若干根火柴，也可以一堆全部取走，但不允许跨堆取，也不允许不取。 谁取走最后一根火柴为胜利者。

例如：k＝2，n1＝n2＝2，A代表你，P代表计算机，若决定A先取： A：(2,2)→(1,2) {从一堆中取一根} P：(1,2)→(1,1) {从另一堆中取一根} A：(1,1)→(1,0)

P：(1,0)→ (0,0) {P胜利} 如果决定A后取： P：(2,2)→(2,0)

A：(2,0)→ 0,0) {A胜利}

又如k＝3，n1=1，n2＝2，n3＝3，A决定后取： P：(1,2,3)→(0,2,3) A：(0,2,3)→(0,2,2)

A已将游戏归结为(2,2)的情况，不管P如何取A都必胜。

编一个程序，在给出初始状态之后，判断是先取必胜还是先取必败，如果是先取必胜，请输 出第一次该如何取。如果是先取必败，则输出“lose”。 【样例1】 match.in match.out 3 4 3 {表示第一次从第3堆取4个出来，必胜} 3 6 9 3 6 5 {第一次取后的状态} 【样例2】 match.in match.out 4 lose {先取必败} 15 22 19 10 【算法分析】

从问题的描述分析，可以将问题中的k堆火柴棒抽象为k个非负整数，而每取一次火柴棒可抽象为使其中的一个自然数变小，当所有的数都变为0时，游戏结束，最后—次取火柴棒的人为胜方。 当k较小，且k堆火柴棒也都较小时，可使用递推的方法来处理这个问题，具体做法是从终了状态(全零)反推出初始状态的值是先取必胜还是先取必败，因为某一状态的值可以从它的所有的取一次后的下一状态得到，如果某状态的所有的下一状态都为先取必败，则这一状态为先取必胜，否则为先取必败。 但当k和ni都很大时，上述方法很难行得通，为了解决这个问题，首先引进关于n个非负整数的奇偶状态的定义：如果把n个非负整数都化成二进制数，然后对n个二进制数按位相加(不进行进位)，若每一位相加的结果都为偶数，则称这n个非负整数的状态为偶状态，否则称之为奇状态。可以证明：任何一个

3

偶状态在某一个数变小后一定成为奇状态，而对任何一个奇状态，必定可以通过将某一个数的值变小，使得改变后的状态成为偶状态。前一种情况是显然的，因为一个数变小以后其对应的二进制数至少有一位发生改变。这一位的改变就破坏了原来的偶状态。后一种情况可以通过构造的方法来证明，首先对任何一个奇状态，从高位向低位寻找到第一位按位加之和为奇数的二进制位，设这一位为第k位，则n个数的对应的二进制数中至少存在一个数，其第k位为1，将这个二进制数的第k位变成0，则所有二进制数的第k位上的数字之和就变成了偶数。然后再对这个数的比k位低的所有位作如下调整：如果所有二进制数在该位按位加之和为偶数，则不改变该位的值，否则改变该数在该位的值，若原来的值为0，则改为1，若原来的值为1，则改为0，这样就构造出了一个偶状态，并且被改变的那个数一定变小了，因为这个数被改变的所有二进制位中的最高位从1变成了0。

如n＝3时，三堆火柴棒的数量分别为3，6，9，则3＝(0011)2，6＝(0110)2，9＝(1001)2，最高位之和为1，其中9对应的二进制数的最高位为1，将其变为0，次高位之和也是1，9对应的二进制数的次高位为0，根据证明过程将其变为1，最后二位数字之和均为偶数，无需作任何改变，这样9＝(1001)2被变成了(0101)2=5，显然，3=(0011)2，6=(0110)2，5=(0101)2是一个偶状态。

有了前面的分析，一种贪心算法就出来了。程序中用n个包含16个元素的数组（线性表）来存放对每个非负整数对应的二进制数，如b[i, 0]存放第i个数的最低位，n个数的状态取决于它们对应的二进制数的各位数字之和的奇偶性，而各位数字之和的奇偶性只需用0和1来表示，0表示偶，1表示奇。最后的状态(全0)为偶状态，所以开始状态为偶状态时，先取必败，因为先取后局面变成了奇状态，后取方一定可将字取成偶状态，直至取光为止。反之则先取必胜。 【后记】

大家都知道国际象棋特级大师卡斯帕罗夫与IBM公司研制的“深蓝”超级计算机进行国际象棋人机大战的事吧!

有了以上算法后，我们也可以编写出这样一个游戏程序。让程序代表计算机与人做取火柴棒游戏，由人或计算机先取，要求你编的程序能够尽可能使计算机获胜。

3.4 加工生产调度

源程序名 prod.???（pas, c, cpp） 可执行文件名 prod.exe 输入文件名 prod.in 输出文件名 prod.out 【问题描述】

某工厂收到了n个产品的订单，这n个产品分别在A、B两个车间加工，并且必须先在A车间加工后才可以到B车间加工。

某个产品i在A、B两车间加工的时间分别为Ai、Bi。怎样安排这n个产品的加工顺序，才能使总的加工时间最短。这里所说的加工时间是指：从开始加工第一个产品到最后所有的产品都已在A、B两车间加工完毕的时间。 【输入】 第一行仅—个数据n(0第一行一个数据，表示最少的加工时间； 第二行是一种最小加工时间的加工顺序。 【样例】 prod.in 5 3 5 8 7 10

4

6 2 1 4 9 prod.out 34 1 5 4 2 3 【算法分析】

本题是要求一个加工顺序使得总的加工时间最少，而要使加工时间最少，就是让各车间的空闲时间最少。一旦A车间开始加工，便会不停地进行加工(我们不要去管车间是否能够一直生产，因为他们有三班，可以24时间不停地运转)。关键是B车间在生产的过程中，有可能要等待A车间的初加工产品。很显然所安排的第一个产品在A车间加工时，B车间是要等待的，最后一个产品在B车间加工时，A车间已经完成了任务。

要使总的空闲时间最少，就要把在A车间加工时间最短的部件优先加工，这样使得B车间能以最快的速度开始加工；把放在B车间加工时间最短的产品放在最后加工，这样使得最后A车间的空闲时间最少。 设计出这样的贪心法： 设Mi＝min{Ai，Bi}

将M按照由小到大的顺序排序，然后从第一个开始处理，如果Mi=Ai，则将它安排在从头开始的已经安排的生产顺序后面，如果Mi＝Bi，则将它安排在从尾开始的已安排的生产顺序前面。 这种安排是否是最少的加工时间，还要通过数学证明。证明如下：

设S＝图3-1是加工作业i时A车间等待B车间的情况：

图3-1 A等B的情况

图3-2是加工作业i时B车间等待A车间的情形：

图3-2 B等A的情况

假设最佳的方案中，先加工作业Ji，然后再加工作业Jj，则有：

5

T(S,t)AiT(s{Ji},Bimax{tAi,0})AiAjT(S{Ji,Jj},Bjmax{Bimax{tAi,0}Aj,0}) AiAjT(S{Ji,Jj},Tij)TijBjmax{Bimax{tAi,0}Aj,0}BjBiAjmax{max{tAi,0},AjBi}BjBiAjmax{tAi,AjBi,0}BjBiAiAjmax{t,Ai,AiAjBi}如果max{t,Ai,AiAjBi}t，则TijtBiBjAiAj 如果max{t,Ai,AiAjBi}Ai，则TijBiBjAj 如果max{t,Ai,AiAjBi}AiAjBi，则TijBj 如果将作业Ji和作业Jj的加工顺序调整，则有：

T'(S,t)AiAjT(S(Ji,Jj),Tji)

其中，TijBiBjAiAjmax{t,Aj,AiAjBj} 按照上面的假设，有T<=T’，所以有：

max{t,AiAjBi,Ai}max{t,AiAjBj,Aj}

从而有：

AiAjmax{Bi,Aj}AiAjmax{Bj,Ai}

即：max{Bj,Ai}max{Bi,Aj}

这说是所谓的Johnson公式，也就是说在此公式成立的条件下，优先安排任务Ji在Jj之前可以得到最

优解。也就是在A车间加工时间短的安排在前面，在B车间加工时间短的任务安排在后面。

以样例数据为例：

（A1, A2, A3, A4, A5）=（3, 5, 8, 7, 10） （B1, B2, B3, B4, B5）=（6, 2, 1, 4, 9） 则（m1, m2, m3, m4, m5）=（3, 2, 1, 4, 9） 排序之后为：（m3, m2, m1, m4, m5）

处理m3，因为m3=B3，所以m3安排在后面（，，，，3）； 处理m2，因为m2=B2，所以m2安排在后面（，，，2，3）； 处理m1，因为m1=A1，所以m1安排在前面（1，，，2，3）； 处理m4，因为m4=B4，所以m4安排在后面（1，，4，2，3）； 处理m5，因为m5=B5，所以m5安排在后面（1，5，4，2，3）。 从而得到加工的顺序1，5，4，2，3。计算出最短的加工时间34。 【补充说明】 由于本题的原始数据并没有保证数据间没有重复，所以在数据有重复的情况下生产调度安排并不是惟一的。但是最少的加工时间是惟一的。

6

3.5 最大乘积

源程序名 maxmul.???（pas, c, cpp） 可执行文件名 maxmul.exe 输入文件名 maxmul.in 输出文件名 maxmul.out 【问题描述】

一个正整数一般可以分为几个互不相同的自然数的和，如3=1+2，4=1+3，5＝1+4=2+3，6=1+5＝2+4，…。 现在你的任务是将指定的正整数n分解成若干个互不相同的自然数的和，且使这些自然数的乘积最大。 【输入】 只一个正整数n，(3≤n≤10000)。 【输出】 第一行是分解方案，相邻的数之间用一个空格分开，并且按由小到大的顺序。 第二行是最大的乘积。 【样例】 maxmul.in maxmul.out 10 2 3 5 30 【算法分析】

初看此题，很容易想到用回溯法进行搜索，但是这里的n范围比较大，最多到10000，如果盲目搜索，运行时间比较长，效率很低，对于部分数据可能得到结果，对于大部分数据会超时或栈溢出。

先来看看几个n比较小的例子，看能否从中找出规律：

n 5 6 7 8 9 10 分解方案 2 3 2 4 3 4 3 5 2 3 4 2 3 5 最大的乘积 6 8 12 15 24 30 可以发现，将n分解成a1, a2, a3, a4,…, am这m个自然数，该序列为从2开始的一串由小到大的自然数，如果a1为1，则对乘积没有影响，而且使n减少，没有实际意义，只有特殊情况如n为3、4时才可能用上。

设h>＝5，可以证明当将h拆分为两个不相同的部分并且两部分都大于1时两部分的乘积大于h。证明如下：

将h分为两部分：a，h-a其中2<＝a因为h>2*a，所以a*(h-a)-h>2*a*(a-1)-a*a=a*a-2*a=a*(a-2)

又因为a>＝2，所以a*(a-2)>=0，所以a*(h-a)-h>O即a*(h-a)>h。

从上面的证明可以看出，对于指定的正整数，如果其大于等于5，将它拆分为不同的部分后乘积变大，对于中间结果也是如此。因此可以将指定的n，依次拆成a1+a2+a3+a4+…+am，乘积最大。

现在的问题是如何拆分才能保证n＝a1+a2+a3+a4+…+am呢?

可以先这样取：当和不足n时，a1取2，a2取3，…，am-1取m，即从2开始按照自然数的顺序取数，最后剩余的数给am，如果am<=am-1，此时am跟前面的数字出现了重复，则把am从后面开始平均分布给前面的m-1个数。为什么要从后面开始往前呢?同样是考虑数据不出现重复的问题，如果是从前面往后面来平均分配，如2加上1以后变成3，就跟后面的已有的3出现了重复。这样操作到底是否正确、是否能保

7

证乘积最大呢?还要加以证明。证明过程如下：

设两个整数a，b的和为2s，且a<>b，设a＝s-1，则b＝s+1，a*b=(s-1)*(s+1)=s2-1，如果a=s-2，则b＝s+2，a*b＝(s-2)*(s+2)＝s2-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，分解之后的各项乘积位数比较多，超过普通的数据类型的位数，所以要用到高精度运算来进行整数的乘法运算，将结果保存在数组里。

本题的贪心策略就是： 要使乘积最大，尽可能地将指定的n(n>4)拆分成从2开始的连续的自然数的和，如果最后有剩余的数，将这个剩余的数在优先考虑后面项的情况下平均分给前面的各项。

基本算法描述如下： （1）拆分过程 拆分的数a先取2； 当n>a时做 Begin 选择a作为一项； a增加1； n减少a； End； 如果n>0，那么将n从最后一项开始平均分给各项； 如果n还大于0，再从最后一项开始分一次； （2）求乘积 设置一个数组来存放乘积，初始状态位数为1，结果为1； 将上面拆分的各项依次跟数组各项相乘并考虑进位；

8

3.6 种树

源程序名 trees.???（pas, c, cpp） 可执行文件名 trees.exe 输入文件名 trees.in 输出文件名 trees.out 【问题描述】

一条街的一边有几座房子。因为环保原因居民想要在路边种些树。路边的地区被分割成块，并被编号成1..N。每个部分为一个单位尺寸大小并最多可种一棵树。每个居民想在门前种些树并指定了三个号码B，E，T。这三个数表示该居民想在B和E之间最少种T棵树。当然，B≤E，居民必须记住在指定区不能种多于区域地块数的树，所以T≤E-B+l。居民们想种树的各自区域可以交叉。你的任务是求出能满足所有要求的最少的树的数量。 写一个程序完成以下工作： * 从trees.in读入数据 * 计算最少要种树的数量和位置 * 把结果写到trees.out 【输入】 第一行包含数据N，区域的个数(0【算法分析】

不难想到下面的贪心算法：按照每个区间的右端点排序，从左向右扫描，把每个区间内的树都尽量种在该区间的右端，由于后一个区间的右端不在这个区间的右端的左边(排序)，可以保证这些树尽可能多地被下面的区间利用到。

扫描需要的时间为O(h)，更新需要的时间为O(n)，所以总的时间复杂度为O(n*h)。

9

3.7 餐巾

源程序名 napkin.???（pas, c, cpp） 可执行文件名 napkin.exe 输入文件名 napkin.in 输出文件名 napkin.out 【问题描述】

一个餐厅在相继的N天里，第i天需要Ri块餐巾(i=l，2，…，N)。餐厅可以从三种途径获得餐巾。 (1)购买新的餐巾，每块需p分；

(2)把用过的餐巾送到快洗部，洗一块需m天，费用需f分(f(3)把餐巾送到慢洗部，洗一块需n天(n>m)，费用需s分(s在每天结束时，餐厅必须决定多少块用过的餐巾送到快洗部，多少块送慢洗部。在每天开始时，餐厅必须决定是否购买新餐巾及多少，使洗好的和新购的餐巾之和满足当天的需求量Ri，并使N天总的费用最小。 【输入】

输入文件共3行，第1行为总天数；第2行为每天所需的餐巾块数；第3行为每块餐巾的新购费用p，快洗所需天数m，快洗所需费用f，慢洗所需天数n，慢洗所需费用s。 【输出】

输出文件共n+1行。第1行为最小的费用。下面的n行为从第1天开始每天需要的总餐巾数、需购买的新餐巾数、结束时往快、慢洗部送洗的餐巾数以及用到的来自快洗的餐巾数和来自慢洗的餐巾数。 【样例】 napkin.in napkin.out 3 3 2 4 3 3 1 2 0 0 10 1 6 2 3 2 1 2 0 1 0 4 0 0 0 2 2 【算法分析】

在思考这个问题时，一般容易想到从洗的角度去思考，这就必然要对每天的餐巾来源进行分类穷举，当天数较长，每天需求量较大时，穷举的数量级至少为每天的餐巾数之积，程序很难在规定时间内运行出最优解。如果从买的角度去思考这个问题，则该问题就变得十分简单。在确定要买的餐巾数之后，显然这些餐巾购买得越早，被反复利用的可能就越大。也就是说，这些餐巾必须在最早的几天中购买，余下的缺口用洗出来的餐巾来填补，对每天用下来的餐巾，假设全部都送洗，但送洗时不确定其状态，即它们有可能被快洗，有可能被慢洗，也可能不用洗，其状态在今后被选用时再确定。在确定每天的需求时，除去买的，剩下的首先要选用慢洗为好。这种餐巾有多少应用多少，不够再选用快洗出来的餐巾。选用快洗出来的餐巾时，应选用最近的若干天中才快洗出来的餐巾，这样可以保证有更多的餐巾被慢洗出来。这就是我 们的贪心思想。 对所要购买的餐巾数进行穷举，开始时其值为所需用餐巾数之和，当购买量太少而周转不过来时，程序结束。在确定了购买的餐巾总数后，按上述算法构造出最小费用方案，所有的最小费用方案中的最优解即为问题的解。程序(见本书光盘)中数组need存放每天需用的餐巾数，数组fromslow记录每天来自慢洗的餐巾数。数组fromfast记录每天来自快洗的餐巾数，数组buy记录每天购买的餐巾数。变量restslow存储当天可供选用的已经慢洗好的餐巾数。这个算法的数量级为O(n)，其中n为所有天中需用的餐巾数之总和。

10

3.8 马拉松接力赛

源程序名 marathon.???（pas, c, cpp） 可执行文件名 marathon.exe 输入文件名 marath.in 输出文件名 marath.out 【问题描述】 某城市冬季举办环城25km马拉松接力赛，每个代表队有5人参加比赛，比赛要求每个的每名参赛选手只能跑一次，一次至少跑1km、最多只能跑10km，而且每个选手所跑的公里数必须为整数，即接力的地方在整公里处。 刘老师作为学校代表队的教练，精心选择了5名长跑能手，进行了训练和测试，得到了这5名选手尽力连续跑1km、2km、…、10km的所用时间。现在他要进行一个合理的安排，让每个选手跑合适的公里数，使学校代表队跑完25km所用的时间最短。根据队员的情况，这个最短的时间是惟一的，但安排方案可能并不惟一。 根据测试情况及一般运动员的情况得知，连续跑1km要比连续跑2km速度快，连续跑2km又要比连续跑3km速度快……也就是说连续跑的路程越长，速度越慢，当然也有特殊的，就是速度不会变慢，但是绝不可能变快。 【输入】 5行数据，分别是1到5号队员的测试数据，每行的10个整数，表示某一个运动员尽力连续跑1km、2km、…、10km所用的时间。 【输出】 两行，第一行是最短的时间，第二行是五个数据，分别是1到5号队员各自连续跑的公里数。 【样例】 marath.in marath.out 333 700 1200 1710 2240 2613 3245 3956 4778 59 9748 300 610 960 1370 1800 2712 3834 4834 5998 7682 6 5 5 4 5 298 612 990 1560 2109 26 3790 4747 5996 7654 2 577 0 1381 1976 2734 3876 5678 60 9876 312 633 995 1467 1845 2634 3636 4812 5999 8123 【算法分析】

初看此题，好象是一个排列问题，选取5个10之间的数，共有10*10*10*10*10＝100000种情况，对每一种情况，再看其和是否为25，在和为25的情况下再计算所用的总时间，找出其中最少的。

这种枚举的方法，肯定能找到最优解，但是这样做的效率不高，执行时间长，这里是5个选手还行，如果更多，如15个选手，就要对l015种可能情况进行判定，再快的计算机也要较长的时间来执行。 因为运动员连续跑一公里要比连续跑两公里速度快、连续跑两公里又要比连续跑三公里速度快……也就是说连续跑的路程越长，速度越慢，所以我们可以将每个选手的所跑时间进行分段处理，计算出各自所跑每一公里所用的时间。又因为要求每个选手至少跑一公里，先给每一个人分配一公里。剩下的里程由哪个选手来跑呢?这时检查各自所跑第二公里所用的时间，哪个用的时间最短就选这个选手继续跑一公里，因为这样做可以保证当前所用的时间最少，这个所手所跑的公里数增加1。下一公里继续用这种方法选，看当前要跑一公里哪个用的时间最短就选谁，选了谁，谁所跑的公里数增加l，下面要检查的时间段就是他的下一段……如此反复直到25公里分配完为止。

对于每个运动员跑各公里所用的时间不一定要单独计算出来，如它跑第5公里所用的时间等于他连续跑完5公里所用的时间减去他连续跑4公里所用的时间。 本题所用的贪心策略就是：

先分配每个运动员跑一公里；剩下的20公里始终选择所有运动员当中下一公里跑的时间最短的，直到分配完。

这样局部的最优保证整体的最优。

11

3.9 线性存储问题

源程序名 storage.???（pas, c, cpp） 可执行文件名 storage.exe 输入文件名 storage.in 输出文件名 storage.out 【问题描述】

磁带等存储介质存储信息时基本上都是一种线性存储的方式，线性存储方式虽然简单，但查询检索时往往要经过一些其它信息，不象磁盘等存储介质在目录区找到后可直接定位到某一区城，因此线性存储总有它的局限性。但是由于磁带等线性存储有简单、保存时间相对较长等优点，现在仍然在使用。

如果有n段信息资料要线性存储在某种存储介质上，它们的长度分别是L1，L2，…，Ln，存储介质能够保存下所有这些信息，假设它们的使用(查询检索)的频率分别是F1，F2，…，Fn，要如何存储这些信息资料才能使平均检索时间最短。

你的任务就是编程安排一种平均检索时间最短的方案。 【输入】

第一行是一个正整数n(n<10000)，接下来是n行数据，每行两个整数分别是第1段信息的长度(1到10000之间)和使用的频率(万分比，在0到9000之间)，总的频率之和为10000。 所输入数据均不要判错。 【输出】 依次存储信息段的编号。每个数据之间用一个空格隔开。 【样例】 storage.in storage.out 5 4 1 3 5 2 10 4000 20 1000 30 1000 35 1500 12 2500 【算法分析】 根据统计的基本原理，n段信息资料的使用（查询检索）的频率之和应为1，即F1+F2+…+Fn=1，如果总的检索次数为m，第I段信息资料使用的次数为m*Fi，设平均检索速度为v单位长度/单位时间，而它的长度为Li，每次所用的时间为Ti-1+Li/V，其中Ti-1为通过安排在第I个信息段前面的所有信息所要的时间，访问信息段I所有次数总的时间时： m*Fi*(Ti-1+Li/v)。

因为上表达式中m、v可看作是常数，所以单一访问时间Fi与Li及前面的安排有关，每段信息均是这样，由此我们可采用如下的贪心方法：

根据(频率*长度)进行由大到小的排序，然后根据这个排序安排某一信息段在相应位置，从而得到的总的检索时间最短，也就是平均检索时间最短。

12

3.10扇区填数

源程序名 fan.???（pas, c, cpp） 可执行文件名 fan.exe 输入文件名 fan.in 输出文件名 fan.out 【问题描述】

有一个圆，当输入一个整数n(1≤n≤6)后，它被分成n个扇区，请你为每一扇区选择一个自然数(大于0的整数)。

向各个扇区放入数之后，你可以从单个扇区中选出—个数，也可以从相邻的两个或多个扇区中各选一个数，相加后形成一个新的数，请使用这些整数形成一个连续的整数序列，：1，2，3，…，i，你的任务是使i尽可能地大。 【输入】

只一个整数n(1<＝n<＝6)。 【输出】

第一行是最大的i，接下来的几行是所有能达到最大i的填法。 由于圆里不分顺序，所以同一种填法可以有多种输出。为了减少这种情况，这里规定从1，开始输出(因为连续数里要有1，所以所填的数中肯定有1)。 【样例】 fan.in fan.out 1 1 1 【算法分析】

假设圆已经被分成了n个扇区，并且已经在这n个扇区中填好了数字，先来看看填好数字后最多有多少种选择连续的数字并求和的方法，以N＝4为例： 单独选一个，有n种即1、2、3、4； 选择相邻两个也有n种即12、23、34、41

选择相邻三个也有n种即123、234、341、412； 选择相邻四个只有一种即1234。

总共有n*(n-1)+1种，当n=4时有13种。

如果每一种选择所求的和都不同，那么能够构成的最多有n*(n-1)+1个不同的数。我们当然希望能够达到的最大的连续数就是从1到n*(n-1)+1了，如N=4时就是1到13。

现在的问题是如何保证这n*(n-1)+1个数就是从1到n*(n-1)+1。在填数时首先填1，接下来的n-1个数都保证不同且最小为2，再看其他的取相邻的多个数的情况了。在n<＝6的情况下都能满足这个要求，对于n>6时就不一定了。

从这种最优策略出发，再结合回溯法找出所有可能的情况。

13