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

贪心法习题汇总贪心法习题汇总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的自然顺序排列的，则这个问题就是求以下公式的最小值： 如果用穷举的方法求解，就需要我们产生n个人的所有不同排列，然后计算每种排列所需要等待的时间之和，再“打擂台”得到最小值，但这种方法需要进行n!次求和以及判断，时间复杂度很差！ 其实，我们认真研究一下上面的公式，发现可以改写成如下形式： 这个公式何时取最小值呢？对于任意一种排列k1, k2, k3, …, kn，当≤≤≤…≤时，total取到最小值。

如何证明呢？方法如下： 因为 假设i

当然，每个游戏本身都很简单，保证每个参赛者都能在一个时段内完成，而且都必须从整时段开始主持人只是想考考每个参赛者如何安排组织自己做游戏的顺序作为参赛者，小伟很想赢得冠军，当然更想赢取最多的钱！注意：比赛绝对不会让参赛者赔钱!【输入】 输入文件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 本题也可以有另外一种贪心算法，即先把所有的数据按照结束时间的先后排序，然后从前向后扫描 当扫描到第n个时段，发现里面所分配的任务的结束时间等于n-1，那么就说明在前面这些任务中必须舍弃一个，于是再扫描第1～n这n个时段，挑出一个最小的去掉并累加扣款值，然后再去调整排列顺序，让后面的元素填补前面的空缺，具体实现请看下面的参考程序23.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个非负整数的状态为偶状态，否则称之为奇状态可以证明：任何一个偶状态在某一个数变小后一定成为奇状态，而对任何一个奇状态，必定可以通过将某一个数的值变小，使得改变后的状态成为偶状态前一种情况是显然的，因为一个数变小以后其对应的二进制数至少有一位发生改变这一位的改变就破坏了原来的偶状态后一种情况可以通过构造的方法来证明，首先对任何一个奇状态，从高位向低位寻找到第一位按位加之和为奇数的二进制位，设这一位为第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 6 2 1 4 9 prod.out 34 1 5 4 2 3【算法分析】 本题是要求一个加工顺序使得总的加工时间最少，而要使加工时间最少，就是让各车间的空闲时间最少一旦A车间开始加工，便会不停地进行加工(我们不要去管车间是否能够一直生产，因为他们。