首页 > 试题广场 >

发奖金

[编程题]发奖金
  • 热度指数：7149 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解 
 狐进行了一次黑客马拉松大赛，全公司一共分为了N个组，每组一个房间排成一排开始比赛，比赛结束后没有公布成绩，但是每个组能够看到自己相邻的两个组里比自己成绩低的组的成绩，比赛结束之后要发奖金，以1w为单位，每个组都至少会发1w的奖金，另外，如果一个组发现自己的奖金没有高于比自己成绩低的组发的奖金，就会不满意，作为比赛的组织方，根据成绩计算出至少需要发多少奖金才能让所有的组满意。


输入描述:
每组数据先输入N，然后N行输入N个正整数，每个数表示每个组的比赛成绩。


输出描述:
输出至少需要多少w的奖金
示例1

输入

10
20 
32 
12 
32 
45 
11 
21 
31 
41 
33

输出

20
算法知识视频讲解
添加回答
推荐
咕米乐头像 咕米乐

    对于给定的一堆成绩，从开始往后，第一个初始化为 1W ，依次向后初始化 i +1 的 money 值，

当 i 对应的分数比 i+1 的分数小时， i+1 应该拿到更多的前，所以有 money[i+1]=money[i]+1;

当 i 对应的分数跟 i+1 相等时，反正也看不到，将 money[i+1] 设为 1 ；

当 i 对应的分数比 i +1 大时： money[i+1] 应该是此时较小的，将其设为 1 ，但是可能后面的跟他相同或比他小，因此要将后面分数递增的那些 money 跟新一下，此处采用一个 for 循环，循环从 k=i+1 开始，当 score[k-1]>score[k]&&money[k]+1>money[k-1] 时才 -- ，注意与后面的条件，是为了判断 money 值可能的断崖式下降（因为起始 money[i+1] 设为 1 了，可能比 money[i] 小很多）。满足条件将其值加 1.

最后累加

#include<iostream>
#include <vector>

using namespace std;

int main(){

int N;
while (cin >> N){
vector<int>score;
vector<int>money(N, 0);
for (int i = 0; i != N; i++){
int temp;
cin >> temp;
score.push_back(temp);
}
money[0] = 1;
for (int i = 0; i != N - 1; i++){
if (score[i]<score[i + 1]){
money[i + 1] = money[i] + 1;
}
else if (score[i]>score[i + 1]){
money[i + 1] = 1;
if (money[i] <= money[i + 1]){
for (int k = i + 1; score[k - 1]>score[k]&&money[k]+1>money[k-1]; k--){
money[k - 1] = money[k - 1] + 1;
}
}
}
else{
money[i + 1] =1;
}
}
int sum = 0;
for (int i = 0; i != money.size(); i++){
sum += money[i];
}
cout << sum << endl;
}


return 0;
}

编辑于 2016-04-03 16:38:42 回复(5)
Python
离疏头像 离疏 
while 1:
    try:
        N=int(input())
        score=[int(input()) for i in range(N)]
        reverse=score[::-1]#分数反序排列
        bonus1=[1 for i in range(N)]#初始值均为1
        bonus2=[1 for i in range(N)]
        ans=[]
        for i in range(1,N):#后一个数大于前一个数，则+1
            if score[i]>score[i-1]:
                bonus1[i]=bonus1[i-1]+1
            if reverse[i]>reverse[i-1]:
                bonus2[i]=bonus2[i-1]+1
        bonus2=bonus2[::-1]#反序
        for i in range(N):#取两次排序中的较大值
            ans.append(max(bonus1[i],bonus2[i]))
        print(sum(ans))
    except:
        break

发表于 2018-08-30 14:33:16 回复(0)
Python
正在卷的马里奥头像 正在卷的马里奥 
import sys
if __name__ == "__main__":
    grade = []
    for i in sys.stdin:
        grade.append(int(i.strip('\n')))
    grade_re = grade.copy()
    grade_re.reverse()
    re1 = []
    re2 = []
    for i in range(1,grade[0]+1):
        if i == 1:
            re1.append(1)
            continue
        if grade[i-1] < grade[i]:
            re1.append(re1[i-2]+1)
        elif grade[i-1] == grade[i]:
            re1.append(re1[i-2])
        else:
            re1.append(1)

    for i in range(0,len(grade_re)-1):
        if i == 0:
            re2.append(1)
            continue
        if grade_re[i-1] < grade_re[i]:
            re2.append(re2[i-1]+1)
        elif grade_re[i-1] == grade_re[i]:
            re2.append(re2[i-1])
        else:
            re2.append(1)
    re2.reverse()
    res = [max(a,b) for a,b in zip(re1,re2)]
    print(sum(res))
本地测试没毛病，但是在这输出为空，不知道为啥。。。
发表于 2018-08-22 18:22:19 回复(0)
提交观点

问题信息

贪心 数组 排序
来自：搜狐2016研发工程师编程题
难度：
2条回答 21693浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号