第六章 贪心算法.pdfVIP

第六章 贪心算法 【上机练习】 1、排队接水(water) 【问题描述】 有n个人在一个水龙头前排队接水，假如每个人接水的时间为Ti，请编程找出这n个人排队的一种顺序， 使得n个人的平均等待时间最小。 【输入格式】 输入文件共两行，第一行为n；第二行分别表示第1 个人到第n个人每人的接水时间T ，T ，…，T ，每 1 2 n 个数据之间有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 532.00 2、最大整数（Noip1998 连接多位数） 【问题描述】 设有n个正整数（n≤20），将它们联接成一排，组成一个最大的多位整数。 例如：n=3时，3个整数13，312，343联接成的最大整数为 又如：n=4时，4个整数7，13，4，246联接成的最大整数为：7424613 【输入格式】 n n个数 【输出格式】 联接成的多位数 【输入样例】 3 13 312 343 【输出样例】 3、纪念品分组(NOIP2007) 【题目描述】 元旦快到了，校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得的纪念 品价值相对均衡，他要把购来的纪念品根据价格进行分组，但每组最多只能包括两件纪念品，并且每组纪 念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时间内发完所有纪念品，乐乐希望分组的 数目最少。 你的任务是写一个程序，找出所有分组方案中分组数最少的一种，输出最少的分组数目。 【输入格式】 输入文件group.in包含 n+2行： 第1行包括一个整数 w，为每组纪念品价格之和的上限。 第2行为一个整数 n，表示购来的纪念品的总件数。 第3~n+2 行每行包含一个正整数p (5 = p = w)，表示所对应纪念品的价格。 i i 【输出格式】 输出文件group.out仅一行，包含一个整数，即最少的分组数目。 【输入输出样例】 group.in group.out 100 6 9 90 20 20 30 50 60 70 80 90 【限制】 50%的数据满足：1 = n = 15 100%的数据满足：1 = n = 30000, 80 = w = 200 4、合并果子(Noip2004) 【问题描述】 在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定 把所有的果子合成一堆。 每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所 有的果子经过 n-1 次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体 力之和。 因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重 量都为 1，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的 体力最少，并输出这个最小的体力耗费值。 例如有3种果子，数目依次为1，2，9。可以先将 1、2堆合并，新堆数目为3，耗费体力为3。接着，