贪心法习题.docVIP

贪心算法 排队接水 【问题描述】water.pas 有n个人在一个水龙头前排队接水，假如每个人接水的时间为Ti，请编程找出这n个人排队的一种顺序，使得n个人的平均等待时间最小。 【输入】water.in 输入文件共两行，第一行为n，第二行分别表示第1个人到第n个人每人的接水时间T1,T2，……Tn,每个数据之间有1个空格。 【输出】water.out 输出文件有两行，第一行为一种排队顺序，即1到n的一种排列；第二行为这种排列方案下的平均等待时间（输出结果精确到小数点后两位） 【输入样例】 10 56 12 1 99 1000 234 33 55 99 812 【输出样例】 3 2 7 8 1 4 9 6 10 5 291.90 二、智力大冲浪 【问题描述】riddle.pas 小伟报名参加中央电视台的智力大冲浪节目。本次挑战赛吸引了众多参赛者，主持人为了表彰大家的勇气，先奖励每个参赛者m元。先不要太高兴！因为这些钱还不一定都是你的！？接下来主持人宣布了比赛规则： 首先，比赛时间分为n个时段（n=500），它又给出了很多小游戏，每个小游戏都必须在规定期限ti前完成（1=ti=n）。如果一个游戏没能在规定期限前完成，则要从奖励费m元中扣去一部分钱wi，wi为自然数，不同的游戏扣去的钱是不一样的。当然，每个游戏本身都很简单，保证每个参赛者都能在一个时段内完成，而且都必须从整时段开始。主持人只是想考考每个参赛者如何安排组织自己做游戏的顺序。作为参赛者，小伟很想赢得冠军，当然更像赢取最多的钱！注意：比赛绝对不会让参赛者赔钱！ 【输入】riddle.in 共4行。第1行为m，表示一开始奖励给每位参赛者的钱；第2行为n，表示有n个小游戏；第3行有n个数，分别表示游戏1到n的规定完成期限；第4行有n个数，分别表示游戏1到n不能在规定期限前完成的扣款数。 【输出】riddle.out 只有1行。表示小伟能赢取最多的钱额。 【输入样例】 10000 7 4 2 4 3 1 4 6 70 60 50 40 30 20 10 【输出样例】 9950 三、取火柴游戏 【问题描述】match.pas 输入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）的情况，不管如何取A都必胜。 编一个程序，在给出初识状态之后，判断是先取必胜还是先取必败，如果是先取必胜，请输出第一次该如何取。如果是先取必败，则输出“lose”。 输入文件为match.in，输出文件为match.out 【输入样例1】 3 3 6 9 【输出样例1】 4 3 3 6 5 【输入样例2】 4 15 22 19 10 【输出样例2】 lose