qq_22584569
Professor.
2016-05-04 10:21

求解贪心算法相关问题

5

题目1: 已知X1,X2,X3,…,Xn是直线上的点,现希望用固定长度固定数量的木条去覆盖这些点,请编写程序求最多能够覆盖多少点?

输入要求:输入的第1行为三个整数n,m,k,分别表示直线上点的个数,木条的长度以及数量。输入的第2行有n个整数,表示坐标上的点。

输出要求:输出1行,为最多能够覆盖的点的个数。

输入样例:

8 3 2

10 7 6 1 -5 4 18 20

输出样例:

5

题目2:设n为一自然数,n可以分解成若干个不同的自然数的和,这样的分法有很多种,比如n=10, 10可以分解为:10=5+4+1; 10=5+3+2; 10+9+1; 10=8+2; 10=7+3; 10=6+4; 10=7+2+1; 10=6+3+1;…。在所有这些分法中,各加数乘积最大的为30, (10=5+3+2中加数的乘积为5*3*2=30)。试编写程序,求各种分解方法中各加数乘积的最大值。

输入要求:输入只有1行,自然数n。

输出要求:输出也只有1行,所有分解方法中各加数乘积的最大值。

题目3:有n个人参加一个马拉松接力游戏,游戏规定每个人可以根据自己的情况随时终止游戏并由下一个人继续接力。由于每个人的情况不同,即使同一个人也不可能在整个游戏过程中永远保持很好的状态。因此要求他们在比赛前根据每个人的情况需要制定一个接力规则,使整个比赛的时间越少越好。请编写程序帮助他们制定这样的接力方案。
输入要求:输入的第1行有三个整数n,k和m,分别表示参加接力的人的个数,每个人最多可以跑的公里数以及接力赛的距离(以公里为单位)。其后的n行,每行有k个整数,分别表示每个人跑整数1公里,2公里,….,K公里所花费的时间(以秒为单位,整数)。游戏要求每个人都必须参加比赛,且每次只能跑到整数公里后才能换人。
输出要求:输出1个整数,表示这些人跑完整个接力赛最少要花多少时间。

  • 点赞
  • 回答
  • 收藏
  • 复制链接分享

4条回答