贪心算法
排队接水
【问题描述】
有n个人在一个水龙头前排队接水,假如每个人接水的时间为Ti,请编程找出这n个人排队的一种顺序,使得n个人的平均等待时间最小。
【输入】
输入文件共两行,第一行为n,第二行分别表示第1个人到第n个人每人的接水时间T1,T2,……Tn,每个数据之间有1个空格。
【输出】
输出文件有两行,第一行为一种排队顺序,即1到n的一种排列;第二行为这种排列方案下的平均等待时间(输出结果精确到小数点后两位)
【输入样例】
10
56 12 1 99 1000 234 33 55 99 812
【输出样例】
3 2 7 8 1 4 9 6 10 5
二、智力大冲浪
【问题描述】
小伟报名参加中央电视台的智力大冲浪节目。本次挑战赛吸引了众多参赛者,主持人为了表彰大家的勇气,先奖励每个参赛者m元。先不要太高兴!因为这些钱还不一定都是你的!?接下来主持人宣布了比赛规则:
首先,比赛时间分为n个时段(n<=500),它又给出了很多小游戏,每个小游戏都必须在规定期限ti前完成(1<=ti<=n)。如果一个游戏没能在规定期限前完成,则要从奖励费m元中扣去一部分钱wi,wi为自然数,不同的游戏扣去的钱是不一样的。当然,每个游戏本身都很简单,保证每个参赛者都能在一个时段内完成,而且都必须从整时段开始。主持人只是想考考每个参赛者如何安排组织自己做游戏的顺序。作为参赛者,小伟很想赢得冠军,当然更像赢取最多的钱!注意:比赛绝对不会让参赛者赔钱!
【输入】
共4行。第1行为m,表示一开始奖励给每位参赛者的钱;第2行为n,表示有n个小游戏;第3行有n个数,分别表示游戏1到n的规定完成期限;第4行有n个数,分别表示游戏1到n不能在规定期限前完成的扣款数。
【输出】
只有1行。表示小伟能赢取最多的钱额。
【输入样例】
10000
7
4 2 4 3 1 4 6
70 60 50 40 30 20 10
【输出样例】
9950
三、取火柴游戏
【问题描述】
输入k及k个整数n1,n2,……,nk,表示有k堆火柴棒,第i堆火柴棒的根数为ni;接着便是你和计算机取火柴棒的对弈游戏。取的规则是:每次可以从一堆中取走若干根火柴,也可以一堆全部取走,但不允许跨堆取,也不允许不取。谁取走最后
贪心法习题 来自淘豆网m.daumloan.com转载请标明出处.
