贪心法习题汇总

1、精选优质文档-倾情为你奉上贪心法习题汇总排队接水源程序名 .?（, , ）可执行文件名 输入文件名 输出文件名 【问题描述】 有个人在一个水龙头前排队接水，假如每个人接水的时间为，请编程找出这个人排队的一种顺序，使得个人的平均等待时间最小。【输入】 输入文件共两行，第一行为；第二行分别表示第个人到第个人每人的接水时间，每个数据之间有个空格。【输出】 输出文件有两行，第一行为一种排队顺序，即到的一种排列；第二行为这种排列方案下的平均等待时间(输出结果精确到小数点后两位)。【样例】【算法分析】平均等待时间是每个人的等待时间之和再除以，因为是一个常数，所以等待时间之和最小，也就是平均等待时间最小。假

2、设是按照的自然顺序排列的，则这个问题就是求以下公式的最小值：如果用穷举的方法求解，就需要我们产生个人的所有不同排列，然后计算每种排列所需要等待的时间之和，再“打擂台”得到最小值，但这种方法需要进行!次求和以及判断，时间复杂度很差！其实，我们仔细研究一下上面的公式，发现可以改写成如下形式：这个公式何时取最小值呢？对于任意一种排列, , , , ，当时，取到最小值。如何证明呢？方法如下：因为假设<，而<，这是的和为，而把和互换位置，设新的和为，则：我们发现上述恒大于，所以也说明了任何次序的改变，都会导致等待时间的增加。从而证明了我们的设想。既然如此，我们就得到了一种最有贪心策略：把接水

3、时间少的人尽可能排在前面。这样一样，问题的本质就变成：把个等待时间按非递减顺序排列，输出这种排列，并求出这种排列下的平均等待时间。智力大冲浪源程序名 .?（, , ）可执行文件名 输入文件名 输出文件名 【问题描述】 小伟报名参加中央电视台的智力大冲浪节目。本次挑战赛吸引了众多参赛者，主持人为了表彰大家的勇气，先奖励每个参赛者元。先不要太高兴！因为这些钱还不一定都是你的？！接下来主持人宣布了比赛规则： 首先，比赛时间分为个时段()，它又给出了很多小游戏，每个小游戏都必须在规定期限前完成()。如果一个游戏没能在规定期限前完成，则要从奖励费元中扣去一部分钱，为自然数，不同的游戏扣去的钱是不一样的。

4、当然，每个游戏本身都很简单，保证每个参赛者都能在一个时段内完成，而且都必须从整时段开始。主持人只是想考考每个参赛者如何安排组织自己做游戏的顺序。作为参赛者，小伟很想赢得冠军，当然更想赢取最多的钱！注意：比赛绝对不会让参赛者赔钱!【输入】输入文件，共行。第行为，表示一开始奖励给每位参赛者的钱；第行为，表示有个小游戏；第行有个数，分别表示游戏到的规定完成期限；第行有个数，分别表示游戏到不能在规定期限前完成的扣款数。【输出】输出文件，仅行。表示小伟能赢取最多的钱。【样例】【算法分析】 因为不同的小游戏不能准时完成时具有不同的扣款权数，而且是最优解问题，所以本题很容易就想到了贪心法。贪心的主要思想是要

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

6、第这个时段，挑出一个最小的去掉并累加扣款值，然后再去调整排列顺序，让后面的元素填补前面的空缺，具体实现请看下面的参考程序。取火柴游戏源程序名 .?（, , ）可执行文件名 输入文件名 输出文件名 【问题描述】 输入及个整数，表示有堆火柴棒，第堆火柴棒的根数为；接着便是你和计算机取火柴棒的对弈游戏。取的规则如下：每次可以从一堆中取走若干根火柴，也可以一堆全部取走，但不允许跨堆取，也不允许不取。 谁取走最后一根火柴为胜利者。 例如：，代表你，代表计算机，若决定先取： ：()() 从一堆中取一根 ：()() 从另一堆中取一根 ：()() ：() () 胜利 如果决定后取： ：()() ：() ) 胜

7、利 又如，决定后取： ：()() ：()() 已将游戏归结为()的情况，不管如何取都必胜。 编一个程序，在给出初始状态之后，判断是先取必胜还是先取必败，如果是先取必胜，请输出第一次该如何取。如果是先取必败，则输出“”。【样例】 表示第一次从第堆取个出来，必胜 第一次取后的状态【样例】先取必败【算法分析】 从问题的描述分析，可以将问题中的堆火柴棒抽象为个非负整数，而每取一次火柴棒可抽象为使其中的一个自然数变小，当所有的数都变为时，游戏结束，最后次取火柴棒的人为胜方。 当较小，且堆火柴棒也都较小时，可使用递推的方法来处理这个问题，具体做法是从终了状态(全零)反推出初始状态的值是先取必胜还是先取必败

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

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

10、最高位之和为，其中对应的二进制数的最高位为，将其变为，次高位之和也是，对应的二进制数的次高位为，根据证明过程将其变为，最后二位数字之和均为偶数，无需作任何改变，这样()被变成了()，显然，()，()，()是一个偶状态。 有了前面的分析，一种贪心算法就出来了。程序中用个包含个元素的数组（线性表）来存放对每个非负整数对应的二进制数，如, 存放第个数的最低位，个数的状态取决于它们对应的二进制数的各位数字之和的奇偶性，而各位数字之和的奇偶性只需用和来表示，表示偶，表示奇。最后的状态(全)为偶状态，所以开始状态为偶状态时，先取必败，因为先取后局面变成了奇状态，后取方一定可将字取成偶状态，直至取光为止。反

11、之则先取必胜。【后记】大家都知道国际象棋特级大师卡斯帕罗夫与公司研制的“深蓝”超级计算机进行国际象棋人机大战的事吧! 有了以上算法后，我们也可以编写出这样一个游戏程序。让程序代表计算机与人做取火柴棒游戏，由人或计算机先取，要求你编的程序能够尽可能使计算机获胜。加工生产调度源程序名 .?（, , ）可执行文件名 输入文件名 输出文件名 【问题描述】 某工厂收到了个产品的订单，这个产品分别在、两个车间加工，并且必须先在车间加工后才可以到车间加工。 某个产品在、两车间加工的时间分别为、。怎样安排这个产品的加工顺序，才能使总的加工时间最短。这里所说的加工时间是指：从开始加工第一个产品到最后所有的产品都

12、已在、两车间加工完毕的时间。【输入】第一行仅个数据(<<)，表示产品的数量。接下来个数据是表示这个产品在车间加工各自所要的时间(都是整数)。最后的个数据是表示这个产品在车间加工各自所要的时间(都是整数)。【输出】 第一行一个数据，表示最少的加工时间； 第二行是一种最小加工时间的加工顺序。【样例】【算法分析】 本题是要求一个加工顺序使得总的加工时间最少，而要使加工时间最少，就是让各车间的空闲时间最少。一旦车间开始加工，便会不停地进行加工(我们不要去管车间是否能够一直生产，因为他们有三班，可以时间不停地运转)。关键是车间在生产的过程中，有可能要等待车间的初加工产品。很显然所安排的第一个

13、产品在车间加工时，车间是要等待的，最后一个产品在车间加工时，车间已经完成了任务。 要使总的空闲时间最少，就要把在车间加工时间最短的部件优先加工，这样使得车间能以最快的速度开始加工；把放在车间加工时间最短的产品放在最后加工，这样使得最后车间的空闲时间最少。 设计出这样的贪心法： 设， 将按照由小到大的顺序排序，然后从第一个开始处理，如果，则将它安排在从头开始的已经安排的生产顺序后面，如果，则将它安排在从尾开始的已安排的生产顺序前面。 这种安排是否是最少的加工时间，还要通过数学证明。证明如下： 设<，)，是等待加工的作业序列，如果车间开始加工中的产品时，车间还在加工其他产品，时刻后车间就可利

14、用车间加工过的产品。在这样的条件下，加工中任务所要的最短时间(, )(，, )，其中，。图是加工作业时车间等待车间的情况：图 等的情况图是加工作业时车间等待车间的情形：图 等的情况假设最佳的方案中，先加工作业，然后再加工作业，则有：如果，则如果，则如果，则如果将作业和作业的加工顺序调整，则有：其中，按照上面的假设，有<，所以有：从而有：即：这说是所谓的公式，也就是说在此公式成立的条件下，优先安排任务在之前可以得到最优解。也就是在车间加工时间短的安排在前面，在车间加工时间短的任务安排在后面。以样例数据为例：（, , , , ）（, , , , ）（, , , , ）（, , , , ）则（

15、, , , , ）（, , , , ）排序之后为：（, , , , ）处理，因为，所以安排在后面（，）；处理，因为，所以安排在后面（，）；处理，因为，所以安排在前面（，）；处理，因为，所以安排在后面（，）；处理，因为，所以安排在后面（，）。从而得到加工的顺序，。计算出最短的加工时间。【补充说明】由于本题的原始数据并没有保证数据间没有重复，所以在数据有重复的情况下生产调度安排并不是惟一的。但是最少的加工时间是惟一的。最大乘积源程序名 .?（, , ）可执行文件名 输入文件名 输出文件名 【问题描述】 一个正整数一般可以分为几个互不相同的自然数的和，如，。 现在你的任务是将指定的正整数分解成若干个

16、互不相同的自然数的和，且使这些自然数的乘积最大。【输入】只一个正整数，()。【输出】第一行是分解方案，相邻的数之间用一个空格分开，并且按由小到大的顺序。第二行是最大的乘积。【样例】【算法分析】 初看此题，很容易想到用回溯法进行搜索，但是这里的范围比较大，最多到，如果盲目搜索，运行时间比较长，效率很低，对于部分数据可能得到结果，对于大部分数据会超时或栈溢出。先来看看几个比较小的例子，看能否从中找出规律：分解方案最大的乘积 可以发现，将分解成, , , , 这个自然数，该序列为从开始的一串由小到大的自然数，如果为，则对乘积没有影响，而且使减少，没有实际意义，只有特殊情况如为、时才可能用上。 设&g

17、t;，可以证明当将拆分为两个不相同的部分并且两部分都大于时两部分的乘积大于。证明如下： 将分为两部分：，其中<<，两部分的乘积为*()。 *()*()* 因为>*，所以*()>*()*() 又因为>，所以*()>，所以*()>即*()>。从上面的证明可以看出，对于指定的正整数，如果其大于等于，将它拆分为不同的部分后乘积变大，对于中间结果也是如此。因此可以将指定的，依次拆成，乘积最大。现在的问题是如何拆分才能保证呢?可以先这样取：当和不足时，取，取，取，即从开始按照自然数的顺序取数，最后剩余的数给，如果<，此时跟前面的数字出现了重复，则把从后

18、面开始平均分布给前面的个数。为什么要从后面开始往前呢?同样是考虑数据不出现重复的问题，如果是从前面往后面来平均分配，如加上以后变成，就跟后面的已有的出现了重复。这样操作到底是否正确、是否能保证乘积最大呢?还要加以证明。证明过程如下：设两个整数，的和为，且<>，设，则，*()*()，如果，则，*()*()。的绝对值越小，乘积的常数项越大，即乘积越大，上面的序列, , , , , 正好满足了的绝对值最小。但是还要注意两个特例就是和的情况，它们的分解方案分别为，和，乘积分别为和。以为例，先拆分为：，最后一项为，比小，将其分配给前面的一项，得到，所以最大的乘积为*。以为例，拆分为：，正好是

19、连续自然数的和，所以最大乘积为*。再以为例，先拆分为：，因为最后一项为，不比最后第二项大，所以将其平均分给前面的项，优先考虑后面的项，即前面的项各分到，笫项分到，最后是，所以最大的乘积为*。由于可能大到，分解之后的各项乘积位数比较多，超过普通的数据类型的位数，所以要用到高精度运算来进行整数的乘法运算，将结果保存在数组里。本题的贪心策略就是：要使乘积最大，尽可能地将指定的(>)拆分成从开始的连续的自然数的和，如果最后有剩余的数，将这个剩余的数在优先考虑后面项的情况下平均分给前面的各项。基本算法描述如下：（）拆分过程 拆分的数先取； 当>时做 选择作为一项； 增加； 减少； ； 如果&

20、gt;，那么将从最后一项开始平均分给各项； 如果还大于，再从最后一项开始分一次；（）求乘积 设置一个数组来存放乘积，初始状态位数为，结果为； 将上面拆分的各项依次跟数组各项相乘并考虑进位；种树源程序名 .?（, , ）可执行文件名 输入文件名 输出文件名 【问题描述】 一条街的一边有几座房子。因为环保原因居民想要在路边种些树。路边的地区被分割成块，并被编号成。每个部分为一个单位尺寸大小并最多可种一棵树。每个居民想在门前种些树并指定了三个号码，。这三个数表示该居民想在和之间最少种棵树。当然，居民必须记住在指定区不能种多于区域地块数的树，所以。居民们想种树的各自区域可以交叉。你的任务是求出能满足所

21、有要求的最少的树的数量。写一个程序完成以下工作：* 从读入数据* 计算最少要种树的数量和位置* 把结果写到【输入】第一行包含数据，区域的个数(<)；第二行包含，房子的数目(<)；下面的行描述居民们的需要： ，<，。【输出】输出文件第一行写有树的数目，下面的行包括所有树的位置，相邻两数之间用一个空格隔开。【样例】【算法分析】 不难想到下面的贪心算法：按照每个区间的右端点排序，从左向右扫描，把每个区间内的树都尽量种在该区间的右端，由于后一个区间的右端不在这个区间的右端的左边(排序)，可以保证这些树尽可能多地被下面的区间利用到。 扫描需要的时间为()，更新需要的时间为()，所以总的

22、时间复杂度为(*)。餐巾源程序名 .?（, , ）可执行文件名 输入文件名 输出文件名 【问题描述】 一个餐厅在相继的天里，第天需要块餐巾(，)。餐厅可以从三种途径获得餐巾。 ()购买新的餐巾，每块需分； ()把用过的餐巾送到快洗部，洗一块需天，费用需分(<)。如时，第一天送到快洗部的餐巾第二天就可以使用了，送慢洗的情况也如此。 ()把餐巾送到慢洗部，洗一块需天(>)，费用需分(<)。 在每天结束时，餐厅必须决定多少块用过的餐巾送到快洗部，多少块送慢洗部。在每天开始时，餐厅必须决定是否购买新餐巾及多少，使洗好的和新购的餐巾之和满足当天的需求量，并使天总的费用最小。【输入】 输

23、入文件共行，第行为总天数；第行为每天所需的餐巾块数；第行为每块餐巾的新购费用，快洗所需天数，快洗所需费用，慢洗所需天数，慢洗所需费用。【输出】 输出文件共行。第行为最小的费用。下面的行为从第天开始每天需要的总餐巾数、需购买的新餐巾数、结束时往快、慢洗部送洗的餐巾数以及用到的来自快洗的餐巾数和来自慢洗的餐巾数。【样例】【算法分析】 在思考这个问题时，一般容易想到从洗的角度去思考，这就必然要对每天的餐巾来源进行分类穷举，当天数较长，每天需求量较大时，穷举的数量级至少为每天的餐巾数之积，程序很难在规定时间内运行出最优解。如果从买的角度去思考这个问题，则该问题就变得十分简单。在确定要买的餐巾数之后，显

24、然这些餐巾购买得越早，被反复利用的可能就越大。也就是说，这些餐巾必须在最早的几天中购买，余下的缺口用洗出来的餐巾来填补，对每天用下来的餐巾，假设全部都送洗，但送洗时不确定其状态，即它们有可能被快洗，有可能被慢洗，也可能不用洗，其状态在今后被选用时再确定。在确定每天的需求时，除去买的，剩下的首先要选用慢洗为好。这种餐巾有多少应用多少，不够再选用快洗出来的餐巾。选用快洗出来的餐巾时，应选用最近的若干天中才快洗出来的餐巾，这样可以保证有更多的餐巾被慢洗出来。这就是我们的贪心思想。对所要购买的餐巾数进行穷举，开始时其值为所需用餐巾数之和，当购买量太少而周转不过来时，程序结束。在确定了购买的餐巾总数后，

25、按上述算法构造出最小费用方案，所有的最小费用方案中的最优解即为问题的解。程序(见本书光盘)中数组存放每天需用的餐巾数，数组记录每天来自慢洗的餐巾数。数组记录每天来自快洗的餐巾数，数组记录每天购买的餐巾数。变量存储当天可供选用的已经慢洗好的餐巾数。这个算法的数量级为()，其中为所有天中需用的餐巾数之总和。马拉松接力赛源程序名 .?（, , ）可执行文件名 输入文件名 输出文件名 【问题描述】某城市冬季举办环城马拉松接力赛，每个代表队有人参加比赛，比赛要求每个的每名参赛选手只能跑一次，一次至少跑、最多只能跑，而且每个选手所跑的公里数必须为整数，即接力的地方在整公里处。 刘老师作为学校代表队的教练，

26、精心选择了名长跑能手，进行了训练和测试，得到了这名选手尽力连续跑、的所用时间。现在他要进行一个合理的安排，让每个选手跑合适的公里数，使学校代表队跑完所用的时间最短。根据队员的情况，这个最短的时间是惟一的，但安排方案可能并不惟一。根据测试情况及一般运动员的情况得知，连续跑要比连续跑速度快，连续跑又要比连续跑速度快也就是说连续跑的路程越长，速度越慢，当然也有特殊的，就是速度不会变慢，但是绝不可能变快。【输入】行数据，分别是到号队员的测试数据，每行的个整数，表示某一个运动员尽力连续跑、所用的时间。【输出】两行，第一行是最短的时间，第二行是五个数据，分别是到号队员各自连续跑的公里数。【样例】【算法分析

27、】 初看此题，好象是一个排列问题，选取个之间的数，共有*种情况，对每一种情况，再看其和是否为，在和为的情况下再计算所用的总时间，找出其中最少的。 这种枚举的方法，肯定能找到最优解，但是这样做的效率不高，执行时间长，这里是个选手还行，如果更多，如个选手，就要对种可能情况进行判定，再快的计算机也要较长的时间来执行。 因为运动员连续跑一公里要比连续跑两公里速度快、连续跑两公里又要比连续跑三公里速度快也就是说连续跑的路程越长，速度越慢，所以我们可以将每个选手的所跑时间进行分段处理，计算出各自所跑每一公里所用的时间。又因为要求每个选手至少跑一公里，先给每一个人分配一公里。剩下的里程由哪个选手来跑呢?这时

28、检查各自所跑第二公里所用的时间，哪个用的时间最短就选这个选手继续跑一公里，因为这样做可以保证当前所用的时间最少，这个所手所跑的公里数增加。下一公里继续用这种方法选，看当前要跑一公里哪个用的时间最短就选谁，选了谁，谁所跑的公里数增加，下面要检查的时间段就是他的下一段如此反复直到公里分配完为止。 对于每个运动员跑各公里所用的时间不一定要单独计算出来，如它跑第公里所用的时间等于他连续跑完公里所用的时间减去他连续跑公里所用的时间。 本题所用的贪心策略就是： 先分配每个运动员跑一公里；剩下的公里始终选择所有运动员当中下一公里跑的时间最短的，直到分配完。 这样局部的最优保证整体的最优。线性存储问题源程序名

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