贪心法习题汇总.doc

《贪心法习题汇总.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

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

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

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

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

6、先后排序，然后从前向后扫描。当扫描到第个时段，发现里面所分配的任务的结束时间等于，那么就说明在前面这些任务中必须舍弃一个，于是再扫描第～这个时段，挑出一个最小的去掉并累加扣款值，然后再去调整排列顺序，让后面的元素填补前面的空缺，具体实现请看下面的参考程序。取火柴游戏源程序名.???（,,）可执行文件名输入文件名输出文件名【问题描述】输入及个整数，，…，，表示有堆火柴棒，第堆火柴棒的根数为；接着便是你和计算机取火柴棒的对弈游戏。取的规则如下：每次可以从一堆中取走若干根火柴，也可以一堆全部取走，但不允许跨堆取，也不允许不取。谁取走最后一根火柴为胜利者。例如：＝，

7、＝＝，代表你，代表计算机，若决定先取：：()→(){从一堆中取一根}：()→(){从另一堆中取一根}：()→()：()→(){胜利}如果决定后取：：()→()：()→){胜利}又如＝，，＝，＝，决定后取：：()→()：()→()已将游戏归结为()的情况，不管如何取都必胜。编一个程序，在给出初始状态之后，判断是先取必胜还是先取必败，如果是先取必胜，请输出第一次该如何取。如果是先取必败，则输出“”。【样例】{表示第一次从第堆取个出来，必胜}{第一次取后的状态}【样例】{先取必败}【算法分析】从问题的描述分析，可以将问题中的堆火柴棒抽象为个非负整数，而每取一次火柴

8、棒可抽象为使其中的一个自然数变小，当所有的数都变为时