贪心法习题汇总

《贪心法习题汇总》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

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的一种排列；第二行为这种排列方案下的平均等待时间

2、(输出结果精确到小数点后两位)。【样例】water.inwater.out103278149610556121991000234335599812291.90【算法分析】平均等待时间是每个人的等待时间之和再除以n，因为n是一个常数，所以等待时间之和最小，也就是平均等待时间最小。假设是按照1~n的自然顺序排列的，则这个问题就是求以下公式的最小值：如果用穷举的方法求解，就需要我们产生n个人的所有不同排列，然后计算每种排列所需要等待的时间之和，再“打擂台”得到最小值，但这种方法需要进行n!次求和以及判断，时间复杂度很差！其实，

3、我们认真研究一下上面的公式，发现可以改写成如下形式：这个公式何时取最小值呢？对于任意一种排列k1,k2,k3,…,kn，当≤≤≤…≤时，total取到最小值。如何证明呢？方法如下：因为假设i

4、排列，并求出这种排列下的平均等待时间。3.2智力大冲浪源程序名riddle.???（pas,c,cpp）可执行文件名riddle.exe输入文件名riddle.in输出文件名riddle.out【问题描述】小伟报名参加中央电视台的智力大冲浪节目。本次挑战赛吸引了众多参赛者，主持人为了表彰大家的勇气，先奖励每个参赛者m元。先不要太高兴！因为这些钱还不一定都是你的？！接下来主持人宣布了比赛规则：首先，比赛时间分为n个时段(n≤500)，它又给出了很多小游戏，每个小游戏都必须在规定期限ti前完成(1≤ti≤n)。如果一个游戏没

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

6、到n不能在规定期限前完成的扣款数。【输出】输出文件riddle.out，仅1行。表示小伟能赢取最多的钱。【样例】riddle.inriddle.out1000099507424314670605040302010【算法分析】因为不同的小游戏不能准时完成时具有不同的扣款权数，而且是最优解问题，所以本题很容易就想到了贪心法。贪心的主要思想是要让扣款数值大的尽量准时完成。这样我们就先把这些任务按照扣款的数目进行排序，把大的排在前面，先进行放置。假如罚款最多的一个任务的完成期限是k，我们应该把它安排在哪个时段完成呢?应该放在第k

7、个时段，因为放在1～k任意一个位置，效果都是一样的。一旦出现一个不可能在规定时限前完成的任务，则把其扔到最大的一个空时间段，这样必然是最优的，因为不能完成的任务，在任意一个时间段中罚款数目都是一样的，具体实现请看下面的参考程序1。本题也可以有另外一种贪心算法，即先把所有的数据按照结束时间的先后排序，然后从前向后扫描。当扫描到第n个时段，发现里面所分配的任务的结束时间等于n-1，那么就说明在前面这些任务中必须舍弃一个，于是再扫描第1～n这n个时段，挑出一个最小的去掉并累加扣款值，然后再去调整排列顺序，让后面的元素填补前面的

8、空缺，具体实现请看下面的参考程序2。3.3取火柴游戏源程序名match.???（pas,c,cpp）可执行文件名match.exe输入文件名match.in输出文件名match.out【问题描述】输入k及k个整数n1，n2，…，nk，表示有k堆火柴棒，第i堆火柴棒的根数为ni；接着便是你和计算机取火柴棒的对弈游戏。取