简答题

在一个操场的四周摆放着n堆石子。现要将石子有次序地合并成一堆。规定每次至少选2堆最多选k堆石子合并成新的一堆,合并的费用为新的一堆的石子数。试设计一个算法,计算出将n堆石子合并成一堆的最大总费用和最小总费用。 输入数据的第1行有2个正整数n和k,表示有n堆石子,每次至少选2堆最多选k堆石子合并。第2行有n个数,分别表示每堆石子的个数。(贪心算法,要求给出贪心策略)

正确答案

最小费用策略:每次选k堆最小的堆合并
排序:5,9,12,13,16,22,45;13,16,22,26,45;26,45,51;122
费用S=(5+9+12)+(13+16+22)+(26+45+51)=26+51+122=199
最大费用策略:每次选2堆最大的堆合并
排序:5,9,12,13,16,22,45;5,9,12,13,16,67;5,9,12,13,83;5,9,12,96;5,9,108;5,117;122
费用T=67+83+96+108+117+122=593

答案解析

相似试题
  • 对具有n个结点的堆进行插入一个元素运算的时间复杂度为O(n)。

    判断题查看答案

  • 现有5堆石子,石子数依次为3,5,7,19,50,甲乙两人轮流从任一堆中任取(每次只能取自一堆,不能不取),取最后一颗石子的一方获胜。甲先取,问甲有没有获胜策略(即无论乙怎样取,甲只要不失误,都能获胜)?如果有,甲第一步应该在哪一堆里取多少?

    简答题查看答案

  • 基于“学生—选课—课程”数据库中有三个表:学生表(s)包含字段学号(S#)、姓名(sname)、性别(sex)、年龄(age);选课表(SC)包含字段课程号(c#)、学号(S#)、成绩(GRADE);课程表(c)包含字段课程号(C#)、课程名(cname)、教师(teacher)。现要将学生的学号及其平均成绩定义为一个视图,在定义该视图是,所有的SELECT语句将出现()子句。

    多选题查看答案

  • 现要将某工作表的D2单元格的内容复制到J5单元格,下列操作中,错误的是()

    单选题查看答案

  • 现要将某工作表的C3单元格的内容移到E4单元格,下列操作中,错误的是()

    单选题查看答案

  • 目标电影和源电影的资源均已打开。现要将源电影的资源复制到目标电影中,请问下列哪种操作是正确的()

    单选题查看答案

  • 现要将S1服务器上的数据导入到S2服务器上,选择数据源时使用U1用户进行操作,则U1的身份和操作权限由()

    单选题查看答案

  • 在Excel工作表中,C列已设置成日期型,其格式为YYYY-MM-DD,某人的生日是1965年11月15日,现要将其输入到C5单元格,并且要求显示成1965-11-15的形式,下列哪种输入是错误的()

    单选题查看答案

  • 现要将S1服务器上的DB1数据库中的T1表中的数据导入到S2服务器的DB2数据库的T2表中,假设T2表已经建立。在选择目的地时使用U2用户进行操作,则U2必须具有()

    单选题查看答案