贪心法习题汇总参考模板范本.doc

1、贪心法习题汇总贪心法习题汇总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

2、.inwater.out103 2 7 8 1 4 9 6 10 556 12 1 99 1000 234 33 55 99 812291.90【算法分析】平均等待时间是每个人的等待时间之和再除以n，因为n是一个常数，所以等待时间之和最小，也就是平均等待时间最小。假设是按照1n的自然顺序排列的，则这个问题就是求以下公式的最小值：如果用穷举的方法求解，就需要我们产生n个人的所有不同排列，然后计算每种排列所需要等待的时间之和，再“打擂台”得到最小值，但这种方法需要进行n!次求和以及判断，时间复杂度很差！其实，我们认真研究一下上面的公式，发现可以改写成如下形式：这个公式何时取最小值呢？对于任意一种排

3、列k1, k2, k3, , kn，当时，total取到最小值。如何证明呢？方法如下：因为假设ij，而，这是的和为total1，而把ki和kj互换位置，设新的和为total2，则：我们发现上述total恒大于0，所以也说明了任何次序的改变，都会导致等待时间的增加。从而证明了我们的设想。既然如此，我们就得到了一种最有贪心策略：把接水时间少的人尽可能排在前面。这样一样，问题的本质就变成：把n个等待时间按非递减顺序排列，输出这种排列，并求出这种排列下的平均等待时间。3.2智力大冲浪源程序名 riddle.?（pas, c, cpp）可执行文件名 riddle.exe输入文件名 riddle.in输出

4、文件名 riddle.out【问题描述】 小伟报名参加中央电视台的智力大冲浪节目。本次挑战赛吸引了众多参赛者，主持人为了表彰大家的勇气，先奖励每个参赛者m元。先不要太高兴！因为这些钱还不一定都是你的？！接下来主持人宣布了比赛规则： 首先，比赛时间分为n个时段(n500)，它又给出了很多小游戏，每个小游戏都必须在规定期限ti前完成(1tin)。如果一个游戏没能在规定期限前完成，则要从奖励费m元中扣去一部分钱wi，wi为自然数，不同的游戏扣去的钱是不一样的。当然，每个游戏本身都很简单，保证每个参赛者都能在一个时段内完成，而且都必须从整时段开始。主持人只是想考考每个参赛者如何安排组织自己做游戏的顺序

5、。作为参赛者，小伟很想赢得冠军，当然更想赢取最多的钱！注意：比赛绝对不会让参赛者赔钱!【输入】输入文件riddle.in，共4行。第1行为m，表示一开始奖励给每位参赛者的钱；第2行为n，表示有n个小游戏；第3行有n个数，分别表示游戏1到n的规定完成期限；第4行有n个数，分别表示游戏1到n不能在规定期限前完成的扣款数。【输出】输出文件riddle.out，仅1行。表示小伟能赢取最多的钱。【样例】riddle.inriddle.out10000995074 2 4 3 1 4 670 60 50 40 30 20 10【算法分析】 因为不同的小游戏不能准时完成时具有不同的扣款权数，而且是最优解问题

6、，所以本题很容易就想到了贪心法。贪心的主要思想是要让扣款数值大的尽量准时完成。这样我们就先把这些任务按照扣款的数目进行排序，把大的排在前面，先进行放置。假如罚款最多的一个任务的完成期限是k，我们应该把它安排在哪个时段完成呢?应该放在第k个时段，因为放在1k任意一个位置，效果都是一样的。一旦出现一个不可能在规定时限前完成的任务，则把其扔到最大的一个空时间段，这样必然是最优的，因为不能完成的任务，在任意一个时间段中罚款数目都是一样的，具体实现请看下面的参考程序1。 本题也可以有另外一种贪心算法，即先把所有的数据按照结束时间的先后排序，然后从前向后扫描。 当扫描到第n个时段，发现里面所分配的任务的结

7、束时间等于n-1，那么就说明在前面这些任务中必须舍弃一个，于是再扫描第1n这n个时段，挑出一个最小的去掉并累加扣款值，然后再去调整排列顺序，让后面的元素填补前面的空缺，具体实现请看下面的参考程序2。3.3取火柴游戏源程序名 match.?（pas, c, cpp）可执行文件名 match.exe输入文件名 match.in输出文件名 match.out【问题描述】 输入k及k个整数n1，n2，nk，表示有k堆火柴棒，第i堆火柴棒的根数为ni；接着便是你和计算机取火柴棒的对弈游戏。取的规则如下：每次可以从一堆中取走若干根火柴，也可以一堆全部取走，但不允许跨堆取，也不允许不取。 谁取走最后一根火柴

8、为胜利者。 例如：k2，n1n22，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胜利 又如k3，n1=1，n22，n33，A决定后取： P：(1,2,3)(0,2,3) A：(0,2,3)(0,2,2) A已将游戏归结为(2,2)的情况，不管P如何取A都必胜。 编一个程序，在给出初始状态之后，判断是先取必胜还是先取必败，如果是先取必胜，请输出第一次该如何取。如果是先取必败，则输出“

9、lose”。【样例1】match.inmatch.out34 3表示第一次从第3堆取4个出来，必胜3 6 93 6 5第一次取后的状态【样例2】match.inmatch.out4lose先取必败15 22 19 10【算法分析】 从问题的描述分析，可以将问题中的k堆火柴棒抽象为k个非负整数，而每取一次火柴棒可抽象为使其中的一个自然数变小，当所有的数都变为0时，游戏结束，最后次取火柴棒的人为胜方。 当k较小，且k堆火柴棒也都较小时，可使用递推的方法来处理这个问题，具体做法是从终了状态(全零)反推出初始状态的值是先取必胜还是先取必败，因为某一状态的值可以从它的所有的取一次后的下一状态得到，如果某

10、状态的所有的下一状态都为先取必败，则这一状态为先取必胜，否则为先取必败。 但当k和ni都很大时，上述方法很难行得通，为了解决这个问题，首先引进关于n个非负整数的奇偶状态的定义：如果把n个非负整数都化成二进制数，然后对n个二进制数按位相加(不进行进位)，若每一位相加的结果都为偶数，则称这n个非负整数的状态为偶状态，否则称之为奇状态。可以证明：任何一个偶状态在某一个数变小后一定成为奇状态，而对任何一个奇状态，必定可以通过将某一个数的值变小，使得改变后的状态成为偶状态。前一种情况是显然的，因为一个数变小以后其对应的二进制数至少有一位发生改变。这一位的改变就破坏了原来的偶状态。后一种情况可以通过构造的

11、方法来证明，首先对任何一个奇状态，从高位向低位寻找到第一位按位加之和为奇数的二进制位，设这一位为第k位，则n个数的对应的二进制数中至少存在一个数，其第k位为1，将这个二进制数的第k位变成0，则所有二进制数的第k位上的数字之和就变成了偶数。然后再对这个数的比k位低的所有位作如下调整：如果所有二进制数在该位按位加之和为偶数，则不改变该位的值，否则改变该数在该位的值，若原来的值为0，则改为1，若原来的值为1，则改为0，这样就构造出了一个偶状态，并且被改变的那个数一定变小了，因为这个数被改变的所有二进制位中的最高位从1变成了0。 如n3时，三堆火柴棒的数量分别为3，6，9，则3(0011)2，6(01

12、10)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个元素的数组（线性表）来存放对每个非负整数对应的二进制数，如bi, 0存放第i个数的最低位，n个数的状态取决于它们对应的二进制数的各位数字之和的奇偶性，而各位数字之和的奇偶性只需用0和1来表示，0表示偶，1表示

13、奇。最后的状态(全0)为偶状态，所以开始状态为偶状态时，先取必败，因为先取后局面变成了奇状态，后取方一定可将字取成偶状态，直至取光为止。反之则先取必胜。【后记】大家都知道国际象棋特级大师卡斯帕罗夫与IBM公司研制的“深蓝”超级计算机进行国际象棋人机大战的事吧! 有了以上算法后，我们也可以编写出这样一个游戏程序。让程序代表计算机与人做取火柴棒游戏，由人或计算机先取，要求你编的程序能够尽可能使计算机获胜。3.4加工生产调度源程序名 prod.?（pas, c, cpp）可执行文件名 prod.exe输入文件名 prod.in输出文件名 prod.out【问题描述】 某工厂收到了n个产品的订单，这n

14、个产品分别在A、B两个车间加工，并且必须先在A车间加工后才可以到B车间加工。 某个产品i在A、B两车间加工的时间分别为Ai、Bi。怎样安排这n个产品的加工顺序，才能使总的加工时间最短。这里所说的加工时间是指：从开始加工第一个产品到最后所有的产品都已在A、B两车间加工完毕的时间。【输入】第一行仅个数据n(0n1000)，表示产品的数量。接下来n个数据是表示这n个产品在A车间加工各自所要的时间(都是整数)。最后的n个数据是表示这n个产品在B车间加工各自所要的时间(都是整数)。【输出】 第一行一个数据，表示最少的加工时间； 第二行是一种最小加工时间的加工顺序。【样例】prod.in53 5 8 7

15、106 2 1 4 9prod.out341 5 4 2 3【算法分析】 本题是要求一个加工顺序使得总的加工时间最少，而要使加工时间最少，就是让各车间的空闲时间最少。一旦A车间开始加工，便会不停地进行加工(我们不要去管车间是否能够一直生产，因为他们有三班，可以24时间不停地运转)。关键是B车间在生产的过程中，有可能要等待A车间的初加工产品。很显然所安排的第一个产品在A车间加工时，B车间是要等待的，最后一个产品在B车间加工时，A车间已经完成了任务。 要使总的空闲时间最少，就要把在A车间加工时间最短的部件优先加工，这样使得B车间能以最快的速度开始加工；把放在B车间加工时间最短的产品放在最后加工，这

16、样使得最后A车间的空闲时间最少。 设计出这样的贪心法： 设MiminAi，Bi 将M按照由小到大的顺序排序，然后从第一个开始处理，如果Mi=Ai，则将它安排在从头开始的已经安排的生产顺序后面，如果MiBi，则将它安排在从尾开始的已安排的生产顺序前面。 这种安排是否是最少的加工时间，还要通过数学证明。证明如下： 设SJ1，J2，Jn)，是等待加工的作业序列，如果A车间开始加工S中的产品时，B车间还在加工其他产品，t时刻后B车间就可利用A车间加工过的产品。在这样的条件下，加工S中任务所要的最短时间T(S, t)=minAi+T(s-Ji，Bi+maxt-Ai, 0)，其中，JiS。图3-1是加工作

17、业i时A车间等待B车间的情况：图3-1 A等B的情况图3-2是加工作业i时B车间等待A车间的情形：图3-2 B等A的情况假设最佳的方案中，先加工作业Ji，然后再加工作业Jj，则有：如果，则如果，则如果，则如果将作业Ji和作业Jj的加工顺序调整，则有：其中，按照上面的假设，有T5，可以证明当将h拆分为两个不相同的部分并且两部分都大于1时两部分的乘积大于h。证明如下： 将h分为两部分：a，h-a其中2a2*a，所以a*(h-a)-h2*a*(a-1)-a*a=a*a-2*a=a*(a-2) 又因为a2，所以a*(a-2)=0，所以a*(h-a)-hO即a*(h-a)h。从上面的证明可以看出，对于指

18、定的正整数，如果其大于等于5，将它拆分为不同的部分后乘积变大，对于中间结果也是如此。因此可以将指定的n，依次拆成a1+a2+a3+a4+am，乘积最大。现在的问题是如何拆分才能保证na1+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出现了重复。这样操作到底是否正确、是否能保证乘

19、积最大呢?还要加以证明。证明过程如下：设两个整数a，b的和为2s，且ab，设as-1，则bs+1，a*b=(s-1)*(s+1)=s2-1，如果a=s-2，则bs+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*530。以n=20为例，拆

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，最后是263+4+5+6+8，所以最大的乘积为3*4*5*6*82880。由于n可能大到10000，分解之后的各项乘积位数比较多，超过普通的数据类型的位数，所以要用到高精度运算来进行整数的乘法运算，将结果保存在数组里。本题的贪心策略就是：要使乘积最大，尽可能地将指定的n(n4)拆分成从2开始的连续的自然数的和，如果最后有剩余的

21、数，将这个剩余的数在优先考虑后面项的情况下平均分给前面的各项。基本算法描述如下：（1）拆分过程 拆分的数a先取2； 当na时做 Begin 选择a作为一项； a增加1； n减少a； End； 如果n0，那么将n从最后一项开始平均分给各项； 如果n还大于0，再从最后一项开始分一次；（2）求乘积 设置一个数组来存放乘积，初始状态位数为1，结果为1； 将上面拆分的各项依次跟数组各项相乘并考虑进位；3.6种树源程序名 trees.?（pas, c, cpp）可执行文件名 trees.exe输入文件名 trees.in输出文件名 trees.out【问题描述】 一条街的一边有几座房子。因为环保原因居民想

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

23、T，0BE30000，TE-B+1。【输出】输出文件第一行写有树的数目，下面的行包括所有树的位置，相邻两数之间用一个空格隔开。【样例】trees.intrees.out9541 4 5 8 91 4 24 6 28 9 23 5 2【算法分析】 不难想到下面的贪心算法：按照每个区间的右端点排序，从左向右扫描，把每个区间内的树都尽量种在该区间的右端，由于后一个区间的右端不在这个区间的右端的左边(排序)，可以保证这些树尽可能多地被下面的区间利用到。 扫描需要的时间为O(h)，更新需要的时间为O(n)，所以总的时间复杂度为O(n*h)。3.7餐巾源程序名 napkin.?（pas, c, cpp）可

24、执行文件名 napkin.exe输入文件名 napkin.in输出文件名 napkin.out【问题描述】 一个餐厅在相继的N天里，第i天需要Ri块餐巾(i=l，2，N)。餐厅可以从三种途径获得餐巾。 (1)购买新的餐巾，每块需p分； (2)把用过的餐巾送到快洗部，洗一块需m天，费用需f分(fm)，费用需s分(sf)。 在每天结束时，餐厅必须决定多少块用过的餐巾送到快洗部，多少块送慢洗部。在每天开始时，餐厅必须决定是否购买新餐巾及多少，使洗好的和新购的餐巾之和满足当天的需求量Ri，并使N天总的费用最小。【输入】 输入文件共3行，第1行为总天数；第2行为每天所需的餐巾块数；第3行为每块餐巾的新购

25、费用p，快洗所需天数m，快洗所需费用f，慢洗所需天数n，慢洗所需费用s。【输出】 输出文件共n+1行。第1行为最小的费用。下面的n行为从第1天开始每天需要的总餐巾数、需购买的新餐巾数、结束时往快、慢洗部送洗的餐巾数以及用到的来自快洗的餐巾数和来自慢洗的餐巾数。【样例】napkin.innapkin.out3643 2 43 3 1 2 0 010 1 6 2 32 1 2 0 1 04 0 0 0 2 2【算法分析】 在思考这个问题时，一般容易想到从洗的角度去思考，这就必然要对每天的餐巾来源进行分类穷举，当天数较长，每天需求量较大时，穷举的数量级至少为每天的餐巾数之积，程序很难在规定时间内运行

26、出最优解。如果从买的角度去思考这个问题，则该问题就变得十分简单。在确定要买的餐巾数之后，显然这些餐巾购买得越早，被反复利用的可能就越大。也就是说，这些餐巾必须在最早的几天中购买，余下的缺口用洗出来的餐巾来填补，对每天用下来的餐巾，假设全部都送洗，但送洗时不确定其状态，即它们有可能被快洗，有可能被慢洗，也可能不用洗，其状态在今后被选用时再确定。在确定每天的需求时，除去买的，剩下的首先要选用慢洗为好。这种餐巾有多少应用多少，不够再选用快洗出来的餐巾。选用快洗出来的餐巾时，应选用最近的若干天中才快洗出来的餐巾，这样可以保证有更多的餐巾被慢洗出来。这就是我们的贪心思想。对所要购买的餐巾数进行穷举，开始

27、时其值为所需用餐巾数之和，当购买量太少而周转不过来时，程序结束。在确定了购买的餐巾总数后，按上述算法构造出最小费用方案，所有的最小费用方案中的最优解即为问题的解。程序(见本书光盘)中数组need存放每天需用的餐巾数，数组fromslow记录每天来自慢洗的餐巾数。数组fromfast记录每天来自快洗的餐巾数，数组buy记录每天购买的餐巾数。变量restslow存储当天可供选用的已经慢洗好的餐巾数。这个算法的数量级为O(n)，其中n为所有天中需用的餐巾数之总和。3.8马拉松接力赛源程序名 marathon.?（pas, c, cpp）可执行文件名 marathon.exe输入文件名 marath.

28、in输出文件名 marath.out【问题描述】某城市冬季举办环城25km马拉松接力赛，每个代表队有5人参加比赛，比赛要求每个的每名参赛选手只能跑一次，一次至少跑1km、最多只能跑10km，而且每个选手所跑的公里数必须为整数，即接力的地方在整公里处。 刘老师作为学校代表队的教练，精心选择了5名长跑能手，进行了训练和测试，得到了这5名选手尽力连续跑1km、2km、10km的所用时间。现在他要进行一个合理的安排，让每个选手跑合适的公里数，使学校代表队跑完25km所用的时间最短。根据队员的情况，这个最短的时间是惟一的，但安排方案可能并不惟一。根据测试情况及一般运动员的情况得知，连续跑1km要比连续跑

29、2km速度快，连续跑2km又要比连续跑3km速度快也就是说连续跑的路程越长，速度越慢，当然也有特殊的，就是速度不会变慢，但是绝不可能变快。【输入】5行数据，分别是1到5号队员的测试数据，每行的10个整数，表示某一个运动员尽力连续跑1km、2km、10km所用的时间。【输出】两行，第一行是最短的时间，第二行是五个数据，分别是1到5号队员各自连续跑的公里数。【样例】marath.inmarath.out333 700 1200 1710 2240 2613 3245 3956 4778 58999748300 610 960 1370 1800 2712 3834 4834 5998 76826

30、5 5 4 5298 612 990 1560 2109 2896 3790 4747 5996 7654289 577 890 1381 1976 2734 3876 5678 6890 9876312 633 995 1467 1845 2634 3636 4812 5999 8123【算法分析】 初看此题，好象是一个排列问题，选取5个10之间的数，共有10*10*10*10*10100000种情况，对每一种情况，再看其和是否为25，在和为25的情况下再计算所用的总时间，找出其中最少的。 这种枚举的方法，肯定能找到最优解，但是这样做的效率不高，执行时间长，这里是5个选手还行，如果更多，如1

31、5个选手，就要对l015种可能情况进行判定，再快的计算机也要较长的时间来执行。 因为运动员连续跑一公里要比连续跑两公里速度快、连续跑两公里又要比连续跑三公里速度快也就是说连续跑的路程越长，速度越慢，所以我们可以将每个选手的所跑时间进行分段处理，计算出各自所跑每一公里所用的时间。又因为要求每个选手至少跑一公里，先给每一个人分配一公里。剩下的里程由哪个选手来跑呢?这时检查各自所跑第二公里所用的时间，哪个用的时间最短就选这个选手继续跑一公里，因为这样做可以保证当前所用的时间最少，这个所手所跑的公里数增加1。下一公里继续用这种方法选，看当前要跑一公里哪个用的时间最短就选谁，选了谁，谁所跑的公里数增加l

32、，下面要检查的时间段就是他的下一段如此反复直到25公里分配完为止。 对于每个运动员跑各公里所用的时间不一定要单独计算出来，如它跑第5公里所用的时间等于他连续跑完5公里所用的时间减去他连续跑4公里所用的时间。 本题所用的贪心策略就是： 先分配每个运动员跑一公里；剩下的20公里始终选择所有运动员当中下一公里跑的时间最短的，直到分配完。 这样局部的最优保证整体的最优。3.9线性存储问题源程序名 storage.?（pas, c, cpp）可执行文件名 storage.exe输入文件名 storage.in输出文件名 storage.out【问题描述】 磁带等存储介质存储信息时基本上都是一种线性存储的

33、方式，线性存储方式虽然简单，但查询检索时往往要经过一些其它信息，不象磁盘等存储介质在目录区找到后可直接定位到某一区城，因此线性存储总有它的局限性。但是由于磁带等线性存储有简单、保存时间相对较长等优点，现在仍然在使用。 如果有n段信息资料要线性存储在某种存储介质上，它们的长度分别是L1，L2，Ln，存储介质能够保存下所有这些信息，假设它们的使用(查询检索)的频率分别是F1，F2，Fn，要如何存储这些信息资料才能使平均检索时间最短。你的任务就是编程安排一种平均检索时间最短的方案。【输入】 第一行是一个正整数n(n10000)，接下来是n行数据，每行两个整数分别是第1段信息的长度(1到10000之间

34、)和使用的频率(万分比，在0到9000之间)，总的频率之和为10000。 所输入数据均不要判错。【输出】依次存储信息段的编号。每个数据之间用一个空格隔开。【样例】storage.instorage.out54 1 3 5 210 400020 100030 100035 150012 2500【算法分析】根据统计的基本原理，n段信息资料的使用（查询检索）的频率之和应为1，即F1+F2+Fn=1，如果总的检索次数为m，第I段信息资料使用的次数为m*Fi，设平均检索速度为v单位长度/单位时间，而它的长度为Li，每次所用的时间为Ti-1+Li/V，其中Ti-1为通过安排在第I个信息段前面的所有信息所

35、要的时间，访问信息段I所有次数总的时间时： m*Fi*(Ti-1+Li/v)。 因为上表达式中m、v可看作是常数，所以单一访问时间Fi与Li及前面的安排有关，每段信息均是这样，由此我们可采用如下的贪心方法： 根据(频率*长度)进行由大到小的排序，然后根据这个排序安排某一信息段在相应位置，从而得到的总的检索时间最短，也就是平均检索时间最短。3.10扇区填数源程序名 fan.?（pas, c, cpp）可执行文件名 fan.exe输入文件名 fan.in输出文件名 fan.out【问题描述】有一个圆，当输入一个整数n(1n6)后，它被分成n个扇区，请你为每一扇区选择一个自然数(大于0的整数)。 向

36、各个扇区放入数之后，你可以从单个扇区中选出个数，也可以从相邻的两个或多个扇区中各选一个数，相加后形成一个新的数，请使用这些整数形成一个连续的整数序列，：1，2，3，i，你的任务是使i尽可能地大。【输入】只一个整数n(1n6)。【输出】第一行是最大的i，接下来的几行是所有能达到最大i的填法。由于圆里不分顺序，所以同一种填法可以有多种输出。为了减少这种情况，这里规定从1，开始输出(因为连续数里要有1，所以所填的数中肯定有1)。【样例】fan.infan.out111【算法分析】 假设圆已经被分成了n个扇区，并且已经在这n个扇区中填好了数字，先来看看填好数字后最多有多少种选择连续的数字并求和的方法，

37、以N4为例： 单独选一个，有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，再看其他的取相邻的多个数的情况了。在n6时就不一定了。 从这种最优策略出发，再结合回溯法找出所有可能的情况。17 / 17