刷题刷出新高度,偷偷领先!偷偷领先!偷偷领先! 关注我们,悄悄成为最优秀的自己!

简答题

编程实现:

老师要奖励N名成绩优秀的同学,首先N名同学按随机顺序排成一排,且每名同学都对应一个成绩(成绩各不相同),然后按照如下规则进行奖励。

规则:

1)每名同学至少奖励1支铅笔;

2)每一名同学拿到铅笔后,都会和左右相邻的同学作比较,如果相邻的同学成绩比自己高,那么铅笔数也一定比自己多,如果相邻的同学成绩比自己低,那么铅笔数一定比自己少。(注意每个人成绩都不同) 

当给出要奖励的同学数N,及N名同学的成绩及排序位置,请你按照规则帮助老师计算出最少需要奖励多少支铅笔。

例如:

当N=3,3名同学的成绩分别为:91,92,94

如果3名同学的排序为:91,94,92,最少需要奖励4支铅笔(成绩为91的同学1支,成绩为94的同学2支,成绩为92的同学1支);

如果3名同学的排序为:91,92,94,最少需要奖励6支铅笔(成绩为91的同学1支,成绩为92的同学2支,成绩为94的同学3支)。

输入描述:

第一行输入一个正整数N,N表示要奖励的同学数

第二行输入N个正整数,每个正整数表示一名同学的成绩(成绩各不相同),正整数之间以一个英文逗号隔开,正整数的顺序即代表学生的排序 

输出描述:

输出一个整数,表示N名同学最少需要奖励的铅笔数


样例输入:

3
91,94,92

样例输出:

4

使用微信搜索喵呜刷题,轻松应对考试!

答案:

输入一个正整数N,表示要奖励的同学数。输入N个正整数,表示N名同学的成绩,正整数之间以一个英文逗号隔开,正整数的顺序即代表学生的排序。算法步骤:1. 根据输入的成绩数组,获取成绩的最大值max_score和最小值min_score。2. 初始化一个长度为N+2的数组dp,dp[i]表示成绩为i的同学最少需要奖励的铅笔数。3. 初始化dp[min_score] = 1,dp[max_score] = N。4. 从min_score+1到max_score-1遍历成绩数组,对于每个成绩i,根据规则2,如果i的左边成绩j比i大,则dp[i] = dp[j] + 1,否则如果i的右边成绩k比i小,则dp[i] = dp[k] + 1,否则dp[i] = dp[i-1] + 1。5. 遍历完所有成绩后,dp[max_score]即为最少需要奖励的铅笔数。

解析:

【喵呜刷题小喵解析】:

本题是一道经典的动态规划问题,可以使用动态规划算法来解决。

首先,根据输入的成绩数组,获取成绩的最大值max_score和最小值min_score,这是为了初始化动态规划数组dp的长度。

然后,初始化一个长度为N+2的数组dp,dp[i]表示成绩为i的同学最少需要奖励的铅笔数。根据规则1,成绩为min_score的同学至少奖励1支铅笔,所以dp[min_score] = 1。根据规则2,成绩为max_score的同学的铅笔数一定比其左右相邻的同学都多,所以dp[max_score] = N。

接下来,从min_score+1到max_score-1遍历成绩数组,对于每个成绩i,根据规则2,如果i的左边成绩j比i大,则i的铅笔数一定比j少1,所以dp[i] = dp[j] + 1;否则如果i的右边成绩k比i小,则i的铅笔数一定比k多1,所以dp[i] = dp[k] + 1;否则i的铅笔数一定比其左右相邻的同学都少1,所以dp[i] = dp[i-1] + 1。

最后,遍历完所有成绩后,dp[max_score]即为最少需要奖励的铅笔数。这是因为成绩为max_score的同学的铅笔数一定比其左右相邻的同学都多,所以最少需要奖励的铅笔数就是dp[max_score]。
创作类型:
原创

本文链接:编程实现: 老师要奖励N名成绩优秀的同学,首先N名同学按随机顺序排成一排,且每名同学都对应一个成绩

版权声明:本站点所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明文章出处。

让学习像火箭一样快速,微信扫码,获取考试解析、体验刷题服务,开启你的学习加速器!

分享考题
share