7-5 小H分糖果 (20 分)
小H来到一个小学分糖果，小学生们很听话，站成一排等着分糖果，小H将根据每个人的上次考试分数给一定的糖果，规则如下。
每个人都有自己分数ai，代表上次考试成绩。每个人都至少有一颗糖。如果两个人相邻，分数高的一定比分数低的糖果多
然而小H经费有限，他想知道最少需要多少糖果。
输入格式:
输入第一行包括一个整数n(1≤n≤105)。 接下来n行，每行1个整数ai(1≤ai≤105)表示站在第i位的人的分数。
输出格式:
输出最少需要多少糖果
输入样例:
在这里给出一组输入。例如：
3122
结尾无空行
输出样例:
在这里给出相应的输出。例如：
4
结尾无空行
代码演示：
#include<bits/stdc++.h>using namespace std;const int MAX=1e5+5;int a[MAX];//用于存储学生们的分数int count1[MAX];//用于存储学生们的糖果数int main(){int n;cin>>n;for(int i=0;i<n;i++)count1[i]=1;//由于每个学生都至少有1颗糖，故将存储糖果的数组初始化为1for(int i=0;i<n;i++)cin>>a[i];//输入学生们的分数//先正向循环，判断各个学生右边情况：//即如果该学生右边的学生分数比其高且糖果数比其少，则该学生右边的学生糖果数=该学生糖果数+1for(int i=0;i<n-1;i++){if(a[i+1]>a[i]&&count1[i+1]<=count1[i])count1[i+1]=count1[i]+1;}//先反向循环，判断各个学生左边情况：//即如果该学生左边的学生分数比其高且糖果数比其少，则该学生左边的学生糖果数=该学生糖果数+1for(int i=n-1;i>0;i--){if(a[i-1]>a[i]&&count1[i-1]<=count1[i])count1[i-1]=count1[i]+1;}//总结：左右两次遍历类似于一次遍历同时左右两次判断。long long res=0;for(int i=0;i<n;i++)res+=count1[i];cout<<res<<endl;}
如果觉得《小H分糖果》对你有帮助，请点赞、收藏，并留下你的观点哦！
