厨艺大赛奖金
厨艺大赛奖金
http://www.nowcoder.com/questionTerminal/6da9a72adb3741ac8f2787358ecda265
题解
题目难度：简单难度
知识点：数学逻辑、数组
解析问题：在分析问题时，用a[i]保存每个厨师的评分，num[i]保存每个厨师的奖金。
在解题时，主要有以下思路。
第一：从左向右比较，如果右边的数比左边的数大，则右边给的奖金多1K
第二：从右往左比较，如果左边的数比右边的数大，则左边给的奖金取max（左边奖金，右边奖金+1）
以示例数据为例，整个遍历的流程如下。
| 遍历 | 评分 | 原奖金 | 变化后奖金 |
|---|---|---|---|
| 从左到右 | 60 76 66 76 85 55 61 71 84 62 | 1 1 1 1 1 1 1 1 1 1 | 1 2 1 2 3 1 2 3 4 1 |
| 从右到左 | 60 76 66 76 85 55 61 71 84 62 | 1 2 1 2 3 1 2 3 4 1 | 1 2 1 2 3 1 2 3 4 1 |
整个过程遍历两次遍历，时间复杂度为O（N）
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
//a[]保存每个厨师的评分，num[]保存每个厨师的奖金
int a[n];
int num[n];
for(int i=0;i<n;i++)
{
int x;
cin>>x;
a[i]=x;
num[i]=1;
}
//从左向右比较，如果右边的数比左边的数大，则右边给的奖金多1K
for(int i=0;i<n-1;i++)
if(a[i]<a[i+1])
num[i+1]=num[i]+1;
//从右往左比较，如果左边的数比右边的数大，则左边给的奖金取max（左边奖金，右边奖金+1）
for(int j=n;j>1;j--)
if(a[j-2]>a[j-1])
num[j-2]=max(num[j-2], num[j-1]+1);
int sum=0;
for(int k=0;k<n;k++)
sum+=num[k];
cout<<sum<<endl;
return 0;
}
