首页 > 试题广场 >

发奖金

[编程题]发奖金
  • 热度指数：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)
提交观点

问题信息

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

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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