贪心法习题汇总

1/15贪心法习题汇总排队接水源程序名.???（,,）可执行文件名输入文件名输出文件名【问题描述】有个人在一个水龙头前排队接水，假如每个人接水的时间为，请编程找出这个人排队的一种顺序，使得个人的平均等待时间最小。【输入】输入文件共两行，第一行为；第二行分别表示第个人到第个人每人的接水时间，，…，，每个数据之间有个空格。【输出】输出文件有两行，第一行为一种排队顺序，即到的一种排列；第二行为这种排列方案下的平均等待时间(输出结果精确到小数点后两位)。【样例】【算法分析】平均等待时间是每个人的等待时间之和再除以，因为是一个常数，所以等待时间之和最小，也就是平均等待时间最小。假设是按照的自然顺序排列的，则这个问题就是求以下公式的最小值：niijjnTTTTTTTTTTtotal1121321211)()()(如果用穷举的方法求解，就需要我们产生个人的所有不同排列，然后计算每种排列所需要等待的时间之和，再“打擂台”得到最小值，但这种方法需要进行!次求和以及判断，时间复杂度很差！其实，我们仔细研究一下上面的公式，发现可以改写成如下形式：niinnTinTTTnTnnTtotal11321)1(2)2()1(这个公式何时取最小值呢？对于任意一种排列,,,…,，当1kT≤2kT≤3kT≤…≤nkT时，取到最小值。如何证明呢？方法如下：因为njikkkkkTTjnTinTnnTtotal)1()1()1(21假设，而ikTjkT，这是的和为，而把和互换位置，设新的和为，则：2/15))(())(1())(1())1()1(()1()1(12ijijijjiijkkkkkkkkkkTTijTTjnTTinTjnTinTjnTintotaltotaltotal我们发现上述△恒大于，所以也说明了任何次序的改变，都会导致等待时间的增加。从而证明了我们的设想。既然如此，我们就得到了一种最有贪心策略：把接水时间少的人尽可能排在前面。这样一样，问题的本质就变成：把个等待时间按非递减顺序排列，输出这种排列，并求出这种排列下的平均等待时间。3/15智力大冲浪源程序名.???（,,）可执行文件名输入文件名输出文件名【问题描述】小伟报名参加中央电视台的智力大冲浪节目。本次挑战赛吸引了众多参赛者，主持人为了表彰大家的勇气，先奖励每个参赛者元。先不要太高兴！因为这些钱还不一定都是你的？！接下来主持人宣布了比赛规则：首先，比赛时间分为个时段(≤)，它又给出了很多小游戏，每个小游戏都必须在规定期限前完成(≤≤)。如果一个游戏没能在规定期限前完成，则要从奖励费元中扣去一部分钱，为自然数，不同的游戏扣去的钱是不一样的。当然，每个游戏本身都很简单，保证每个参赛者都能在一个时段内完成，而且都必须从整时段开始。主持人只是想考考每个参赛者如何安排组织自己做游戏的顺序。作为参赛者，小伟很想赢得冠军，当然更想赢取最多的钱！注意：比赛绝对不会让参赛者赔钱!【输入】输入文件，共行。第行为，表示一开始奖励给每位参赛者的钱；第行为，表示有个小游戏；第行有个数，分别表示游戏到的规定完成期限；第行有个数，分别表示游戏到不能在规定期限前完成的扣款数。【输出】输出文件，仅行。表示小伟能赢取最多的钱。【样例】【算法分析】因为不同的小游戏不能准时完成时具有不同的扣款权数，而且是最优解问题，所以本题很容易就想到了贪心法。贪心的主要思想是要让扣款数值大的尽量准时完成。这样我们就先把这些任务按照扣款的数目进行排序，把大的排在前面，先进行放置。假如罚款最多的一个任务的完成期限是，我们应该把它安排在哪个时段完成呢?应该放在第个时段，因为放在～任意一个位置，效果都是一样的。一旦出现一个不可能在规定时限前完成的任务，则把其扔到最大的一个空时间段，这样必然是最优的，因为不能完成的任务，在任意一个时间段中罚款数目都是一样的，具体实现请看下面的参考程序。本题也可以有另外一种贪心算法，即先把所有的数据按照结束时间的先后排序，然后从前向后扫描。当扫描到第个时段，发现里面所分配的任务的结束时间等于，那么就说明在前面这些任务中必须舍弃一个，于是再扫描第～这个时段，挑出一个最小的去掉并累加扣款值，然后再去调整排列顺序，让后面的元素填补前面的空缺，具体实现请看下面的参考程序。4/15取火柴游戏源程序名.???（,,）可执行文件名输入文件名输出文件名【问题描述】输入及个整数，，…，，表示有堆火柴棒，第堆火柴棒的根数为；接着便是你和计算机取火柴棒的对弈游戏。取的规则如下：每次可以从一堆中取走若干根火柴，也可以一堆全部取走，但不允许跨堆取，也不允许不取。谁取走最后一根火柴为胜利者。例如：＝，＝＝，代表你，代表计算机，若决定先取：：()→(){从一堆中取一根}：()→(){从另一堆中取一根}：()→()：()→(){胜利}如果决定后取：：()→()：()→){胜利}又如＝，，＝，＝，决定后取：：()→()：()→()已将游戏归结为()的情况，不管如何取都必胜。编一个程序，在给出初始状态之后，判断是先取必胜还是先取必败，如果是先取必胜，请输出第一次该如何取。如果是先取必败，则输出“”。【样例】{表示第一次从第堆取个出来，必胜}{第一次取后的状态}【样例】{先取必败}【算法分析】从问题的描述分析，可以将问题中的堆火柴棒抽象为个非负整数，而每取一次火柴棒可抽象为使其中的一个自然数变小，当所有的数都变为时，游戏结束，最后—次取火柴棒的人为胜方。当较小，且堆火柴棒也都较小时，可使用递推的方法来处理这个问题，具体做法是从终了状态(全零)反推出初始状态的值是先取必胜还是先取必败，因为某一状态的值可以从它的所有的取一次后的下一状态得到，如果某状态的所有的下一状态都为先取必败，则这一状态为先取必胜，否则为先取必败。但当和都很大时，上述方法很难行得通，为了解决这个问题，首先引进关于个非负整数的奇偶状态的定义：如果把个非负整数都化成二进制数，然后对个二进制数按位相加(不进行进位)，若每一位相加的结果都为偶数，则称这个非负整数的状态为偶状态，否则称之为奇状态。可以证明：任何一个偶状态在某一个数变小后一定成为奇状态，而对任何一个奇状态，必定可以通过将某一个数的值变小，使得改变后的状态成为偶状态。前一种情况是显然5/15的，因为一个数变小以后其对应的二进制数至少有一位发生改变。这一位的改变就破坏了原来的偶状态。后一种情况可以通过构造的方法来证明，首先对任何一个奇状态，从高位向低位寻找到第一位按位加之和为奇数的二进制位，设这一位为第位，则个数的对应的二进制数中至少存在一个数，其第位为，将这个二进制数的第位变成，则所有二进制数的第位上的数字之和就变成了偶数。然后再对这个数的比位低的所有位作如下调整：如果所有二进制数在该位按位加之和为偶数，则不改变该位的值，否则改变该数在该位的值，若原来的值为，则改为，若原来的值为，则改为，这样就构造出了一个偶状态，并且被改变的那个数一定变小了，因为这个数被改变的所有二进制位中的最高位从变成了。如＝时，三堆火柴棒的数量分别为，，，则＝()，＝()，＝()，最高位之和为，其中对应的二进制数的最高位为，将其变为，次高位之和也是，对应的二进制数的次高位为，根据证明过程将其变为，最后二位数字之和均为偶数，无需作任何改变，这样＝()被变成了()，显然，()，()，()是一个偶状态。有了前面的分析，一种贪心算法就出来了。程序中用个包含个元素的数组（线性表）来存放对每个非负整数对应的二进制数，如[,]存放第个数的最低位，个数的状态取决于它们对应的二进制数的各位数字之和的奇偶性，而各位数字之和的奇偶性只需用和来表示，表示偶，表示奇。最后的状态(全)为偶状态，所以开始状态为偶状态时，先取必败，因为先取后局面变成了奇状态，后取方一定可将字取成偶状态，直至取光为止。反之则先取必胜。【后记】大家都知道国际象棋特级大师卡斯帕罗夫与公司研制的“深蓝”超级计算机进行国际象棋人机大战的事吧!有了以上算法后，我们也可以编写出这样一个游戏程序。让程序代表计算机与人做取火柴棒游戏，由人或计算机先取，要求你编的程序能够尽可能使计算机获胜。6/15加工生产调度源程序名.???（,,）可执行文件名输入文件名输出文件名【问题描述】某工厂收到了个产品的订单，这个产品分别在、两个车间加工，并且必须先在车间加工后才可以到车间加工。某个产品在、两车间加工的时间分别为、。怎样安排这个产品的加工顺序，才能使总的加工时间最短。这里所说的加工时间是指：从开始加工第一个产品到最后所有的产品都已在、两车间加工完毕的时间。【输入】第一行仅—个数据()，表示产品的数量。接下来个数据是表示这个产品在车间加工各自所要的时间(都是整数)。最后的个数据是表示这个产品在车间加工各自所要的时间(都是整数)。【输出】第一行一个数据，表示最少的加工时间；第二行是一种最小加工时间的加工顺序。【样例】【算法分析】本题是要求一个加工顺序使得总的加工时间最少，而要使加工时间最少，就是让各车间的空闲时间最少。一旦车间开始加工，便会不停地进行加工(我们不要去管车间是否能够一直生产，因为他们有三班，可以时间不停地运转)。关键是车间在生产的过程中，有可能要等待车间的初加工产品。很显然所安排的第一个产品在车间加工时，车间是要等待的，最后一个产品在车间加工时，车间已经完成了任务。要使总的空闲时间最少，就要把在车间加工时间最短的部件优先加工，这样使得车间能以最快的速度开始加工；把放在车间加工时间最短的产品放在最后加工，这样使得最后车间的空闲时间最少。设计出这样的贪心法：设＝{，}将按照由小到大的顺序排序，然后从第一个开始处理，如果，则将它安排在从头开始的已经安排的生产顺序后面，如果＝，则将它安排在从尾开始的已安排的生产顺序前面。这种安排是否是最少的加工时间，还要通过数学证明。证明如下：设＝，，…，)，是等待加工的作业序列，如果车间开始加工中的产品时，车间还在加工其他产品，时刻后车间就可利用车间加工过的产品。在这样的条件下，加工中任务所要的最短时间(,){({}，{,})}，其中，∈。图是加工作业时车间等待车间的情况：7/15图等的情况图是加工作业时车间等待车间的情形：图等的情况假设最佳的方案中，先加工作业，然后再加工作业，则有：)},,{(})0,}0,max{max{},,{(})0,max{},{(),(ijjijijiijjijiiiiiTJJSTAAAAtBBJJSTAAAtBJsTAtST},,max{}0,,max{}},0,max{max{}0,}0,max{max{ijiijiijijijijijijijjiijijBAAAtAABBBAAtABBBAAtABBAAtBBT如果tBAAAtijii},,max{，则jijiijAABBtT如果iijiiABAAAt},,max{，则jjiijABBT如果ijiijiiBAABAAAt},,max{，则jijBT如果将作业和作业的加工顺序调整，则有：)),,((),('jijijiTJJSTAAtST其中，},,max{jjijjijiijBAAAtAABBT按照上面的假设，有’，所以有：8/15},,max{},,max{jjjiiijiABAAtABAAt从而有：},max{},max{ijjijijiABAAABAA即：},max{},max{jiijABAB这说是所谓的公式，也就是说在此公式成立的条件下，优先安排任务在之前可以得到最优解。也就是在车间加工时间短的安排在前面，在车间加工时间短的任务安排在后面。以样例数据为例：（,,,,）（,,,,）（,,,,）（,,,,）则（,,,,）（,,,,）排序之后为：（,