[传智杯 #2 初赛] 1024 程序员节发橙子
题目描述
每年的 1024 程序员节日，黑马程序员都会举办大型的庆祝活动。今年的程序员节也不例外，每个班级的同学都发了橙子。
班级里有 n 名同学从前到后排成一排，且已经得知了这些同学的成绩，其中第 i 名同学的成绩是ai。班主任想根据同学们上个阶段的考试成绩来评定发橙子的数量。为了激励成绩优秀同学，发橙子时需要满足如下要求：
- 相邻同学中成绩好的同学的橙子必须更多。若相邻的同学成绩一样，则它们分到的数量必须平等。
- 每个同学至少分配一个橙子
由于预算有限，班主任希望在符合要求的情况下发出尽可能少的橙子。请问，至少需要准备多少橙子呢？
输入格式
第一行是一个整数 n，表示学生数量。
接下来一行有 n 个整数，第 i 个整数 ai，表示第 i 个同学的成绩。
输出格式
输出答案，也就是需要最少准备多少个橙子。
输入输出样例
输入 #1复制
5 3 4 5 4 3
输出 #1复制
9
说明/提示
样例 1 解释
每位同学拿到的橙子的数量分别是 1,2,3,2,1所以至少需要准备 9个。
数据规模与约定
对于全部的测试点，保证 1≤n≤106，0≤ai≤10的9次方。
#include <iostream>
#include <math.h>
using namespace std;long long n,sum=0,w=1;int s[1000010],q[1000010];
int main(){cin>>n;for(int i=1;i<=n;i++){cin>>s[i];q[i]=1;//初始化全部都为1个橙子}for(int i=2;i<=n;i++){//先正序遍历，后一个比前一个成绩好的就加一个橙子if(s[i-1]<s[i])q[i]=q[i-1]+1;if(s[i]==s[i-1])//如果成绩一样，就后一个橙子的数量等于前一个的数量q[i]=q[i-1];}for(int i=n;i>=2;i--){//再逆序遍历if(s[i]<s[i-1]) q[i-1]=max(q[i-1],q[i]+1);//如果前一个成绩更好，就比后一个多一个橙子，再和之前正序遍历的橙子数比较，取更大值if(s[i-1]==s[i]) q[i-1]=q[i];//如果相等就前一个等于后一个}for(int i=1;i<=n;i++){sum+=q[i];}//for循环把橙子的数量相加cout<<sum;return 0;
}