首页 > 试题广场 >

厨艺大赛奖金

[编程题]厨艺大赛奖金

热度指数：2645 时间限制：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

输出

算法知识视频讲解

Python

LitterF

leecode标准解法，默写的答案

空间复杂度O(1)，时间复杂度1N

判断一下，如果之前是降低但这次没降，隔断

如果之前是上升这次是不升不降，隔断

注意边界什么的就可以了。

data = [int(x) for x in input().split()]
data.pop(0)
def count(n):
    return n*(n+1)//2

up,down = 0,0
old_d,cur_d = 0,0
res = 0
for i in range(1,len(data)):
    if data[i]>data[i-1]:
        cur_d = 1
    elif data[i]<data[i-1]:
        cur_d = -1
    else:
        cur_d = 0
    if old_d==-1 and cur_d >=0 or old_d==1 and cur_d ==0:
        #先降再平升 或者先升在平
        res+=count(up)+count(down)+max(up,down)
        up,down = 0,0
    #
    if data[i]>data[i-1]:
        up+=1
    elif data[i]<data[i-1]:
        down +=1
    else:
        res+=1
    old_d = cur_d
res+=count(up)+count(down)+max(up,down)+1
print(res)

编辑于 2019-11-06 22:33:48 回复(0)

Python

白色纯度

和分糖果那道题目完全一样！

def score(num):
    res = [1 for _ in range(len(num))]
    for i in range(len(num)-1):
        if num[i]<num[i+1]:
            res[i+1] = res[i]+1
    for j in range(len(num)-2,-1,-1):
        if num[j]>num[j+1]:
            res[j] = max(res[j],res[j+1]+1)
    return sum(res)
if __name__=='__main__':
    num = list(map(int,input().split()))
    person = num[1:]
    print(score(person))

发表于 2019-08-09 19:45:40 回复(0)