首页 > 试题广场 >

厨艺大赛奖金

[编程题]厨艺大赛奖金

热度指数：2652 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

小米食堂每年都会举办一次厨艺大赛，假设参赛的厨师一共有n位（n < 1000），比赛结束后没有公布评分，但是站在领奖台上的一排厨师中每位厨师都能看到与自己相邻的厨师（左或者右）里评分比自己低（看不到比自己分数高的人的分数）的评分。比赛结束之后要发奖金，以1K为单位，每位厨师至少会发1K的奖金，另外，如果一个厨师发现自己的奖金没有高于比自己评分低的厨师的奖金，就会不满意，作为比赛组织方，小米食堂至少需要发放多少奖金才能让所有厨师满意。

输入描述:

每组数据为n+1个正整数单空格分割，其中第一个数为参赛厨师的人数，后面n个数为每位厨师的得分（0-100）

输出描述:

输出至少需要多少K的奖金

示例1

输入

10 60 76 66 76 85 55 61 71 84 62

输出

算法知识视频讲解

牛客192788211号

发表于 2022-01-27 10:21:18

贪心算法，先每个人发放1K，然后遍历，把不满足的厨师的奖金调整到当前满足的状态，然后再遍历，一直到所有厨师都满足。 import java.util.*; public class Main{ public static void main(String[] args){ 展开全文

牛客题解官

发表于 2020-06-05 16:09:51

题解题目难度：简单难度知识点：数学逻辑、数组解析问题：在分析问题时，用a[i]保存每个厨师的评分，num[i]保存每个厨师的奖金。在解题时，主要有以下思路。第一：从左向右比较，如果右边的数比左边的数大，则右边给的奖金多1K第二：从右往左比较，如果左边的数比右边的数大，则左边给的奖金取max（左展开全文