欢乐暑假线上编程比赛第四题：分配糖果

题目详情 有n个小朋友站成一排（编号从0到n-1)，每个小朋友有一个rating值，存放在ratings数组中。老师需要给他们分配糖果，每个小朋友至少需要一颗糖果，对于任意相邻的两个小朋友i和i+1，rating值大的必须比rating值小的分配的糖果多（rating相同的没必要分配一样多的糖果）。 请计算最少需要多少颗糖果，才能完成上述分配。 输入格式： 多组数据，每组数据第一行是一个正整数n。 接下来n行,每行有1个正整数，表示每个小朋友的rating值。所有整数都不超过100000。 输出格式： 每组数据一行，包括一个正整数，表示做少需要的糖果数。 答题说明 输入样例 3 1 2 2 输出样例：

4

关于这道题，整体思路的话比较简单，但是其中有些细节需要额外当心，第一次commit的时候，也是输出错误答案，下面我以一些输入样例来说明有哪些需要当心的。

变量约定：a数组存放输入数据，count表示对应的数分配的最小糖果数

case1：

输入：14445

对于此测试数据，

如果a[i+1]>a[i]，那么count[i+1]=count[i]+1

如果a[i+1]=a[i]，那么对于上述输入，count[i]=1

count最后分布如下：

12112

case2：

输入：144432

如果a[i+1]>a[i]，那么count[i+1]=count[i]+1

如果a[i+1]=a[i] ，那么对于上述输入，count[i]=1

如果a[i+1]<a[i]，那么对于上述输入，count[i]=??这里需要做的就是找到i开始的递减序列的长度，然后count[i],count[i+1],.....count[j]=len,len-1,......1

count最后分布如下：

121321

case3:

输入：14443212345432

如果a[i+1]>a[i]，那么count[i+1]=count[i]+1

如果a[i+1]=a[i] ，那么对于上述输入，count[i]=1

如果a[i+1]<a[i]，那么对于上述输入，count[i]=??这里需要做的就是找到i开始的递减序列的长度，然后count[i],count[i+1],.....count[j]=len,len-1,......1，这里要注意的就是5

此时的糖果数是否比从5开始的递减序列的长度长，如果长的话，不需要更新；否则的话，就需要更新，因为5这里即需要保证前面的递增序列以最小的值递增，也要保证后面递减序列递减到最小值1

count最后分布如下：

12132112345321

大概思路不难，就是在编码的过程中需要注意一些小技巧，参考代码如下（c++ accepted）

#include <iostream>
using namespace std;
int rating[1000001];
int count[1000001];//存放每个人的最小糖果数
void main()
{
    int n;
    while(cin>>n) {
        for(int i=1;i<=n;i++) {
            cin>>rating[i];
        }
        for(int i=1;i<=n;i++) { //这里方便计算，我们增加了一个哨兵作为起始端，也就是count[0]=0,rating[0]
            if(rating[i]>rating[i-1])
                count[i]=count[i-1]+1;
            else if(rating[i]==rating[i-1])
                count[i]=1;
            else {
                int tmp=i;//记录当前开始递减的位置，也就是递减序列的<span style="color:#ff0000;">第二个数</span>的位置
                while(rating[tmp]>rating[tmp+1] && tmp<n) //递减序列终止的位置
                    tmp++;
                int len=tmp-(i-1)+1;//递减序列的长度
                if(count[i-1]<len)
                    count[i-1]=len; //<span style="font-family: Arial, Helvetica, sans-serif;">比较递减序列的长度是否比前面递增序列的最大值大</span>
                len--;
                for(int j=0;j<len;j++) //倒序更新递减序列的糖果数
                    count[tmp-j]=j+1;
                i=tmp;//从递减序列终止的位置继续向后遍历
            }
        }
        int sum=0;
        for(int i=1;i<=n;i++)
            sum += count[i];//求和
        cout<<sum<<endl;
    }
}        

给出一些测试数据供大家对比：