派分糖果 _牛客博客

题解：

考察点：贪心，动态规划，单调栈

常见错误：

如果除去输入只实现一个类的话，这是一个很经典的面试题目，很多同学在面试中都遇到过。但是因为这里的输入跟大家熟知的不太相同，很多同学拿着无从下手。其实面对这种没有给定个数的输入数据，有很多读入方法，其中最常见的就是当成字符串，以 $getline$ 按照一行来读入，然后对字符串进行解析。但是最快的读入方法还是推荐使用 $getchar$ 。 $getchar$ 每次读入 1 byte 的数据，并将其转换为 $char$ 类型的函数，且速度很快，可以用“读入字符——转换为整型”来代替缓慢的读入。同时在读入中修改 $getline$ 只对数字有效，而略过","，我们一般称这种方法为读入优化，有关于更多的知识，可以上OI-wiki去学习。

方法一：

使用一个数组 $dp$ 记录给每个学生的糖果数。初始时，每个学生都分到 $1$ 个糖果，对于当前的学生，如果评分比前一个学生大，但是 $dp$ 值却比前一个学生少，则把 $dp$ 值改为前一个学生的 $dp$ 值加 $1$ ，同理对于后一个学生也是，如果评分比后一个学生大， $dp$ 值却比后一个学生小，改为后一个学生的 $dp$ 值加 $1$ 。同时设置一个变量 $flag$ ，检测 $dp$ 值是否满足要求，如果不满足进行新一轮的迭代，如果满足，则停止。因为对于每个元素，在极限状态下都可能被遍历 $n$ 次，所以时间复杂度是 $O(n^2)$ ，空间复杂度是 $O(n)$

#include "bits/stdc++.h"
using namespace std;
const int maxn=1e5+100;
inline int read(){     //读入优化
    int x=0,f=1;char ch=getchar();
    if(!((ch>='0'&&ch<='9')||(ch==',')||(ch=='\n')||(ch=='\t'))) return INT_MIN;
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,a[maxn],dp[maxn];
int main()
{
    int x;
    while(1){
        x=read();
        if(x==INT_MIN) break;
        a[++n]=x;
    }
    for(int i=1;i<=n;i++) dp[i]=1;
    bool flag=true;
    while(flag){
        flag=false;
        for(int i=1;i<=n;i++){
            if(i!=n&&a[i]>a[i+1]&&dp[i]<=dp[i+1]){
                dp[i]=dp[i+1]+1;
                flag=true;
            }
            if(i!=1&&a[i]>a[i-1]&&dp[i]<=dp[i-1]){
                dp[i]=dp[i-1]+1;
                flag=true;
            }
        }
    }
    int sum=0;
    for(int i=1;i<=n;i++) sum+=dp[i];
    printf("%d\n",sum);
    return 0;
}

方法二：

基于上述方法做进一步优化，上述方法对于每个位置i同时考虑了左邻居和右邻居，但是其实可以将左邻居和右邻居分开来考虑。同样用数组 $dp$ 记录给每个学生的糖果数。初始时，每个学生都分到1个糖果，接着从前往后遍历，找到分数比左邻居高且糖果数小于等于左邻居的学生，更新 $dp[i]=dp[i-1]+1$ 。然后从后往前遍历，找到分数比右邻居高，且 $dp$ 值不大于右邻居的，更新 $dp$ 值为 $dp[i]=dp[i+1]+1$ 。因为只需要扫 $2$ 遍，时间复杂度为 $O(n)$ ，空间复杂度为 $O(n)$

#include "bits/stdc++.h"
using namespace std;
const int maxn=1e5+100;
inline int read(){     //读入优化
    int x=0,f=1;char ch=getchar();
    if(!((ch>='0'&&ch<='9')||(ch==',')||(ch=='\n')||(ch=='\t'))) return INT_MIN;
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,a[maxn],dp[maxn];
int main()
{
    int x;
    while(1){
        x=read();
        if(x==INT_MIN) break;
        a[++n]=x;
    }
    for(int i=1;i<=n;i++) dp[i]=1;
    for(int i=2;i<=n;i++){
        if(a[i]>a[i-1]) dp[i]=dp[i-1]+1;
    }
    for(int i=n-1;i>=1;i--){
        if(a[i]>a[i+1]&&dp[i]<=dp[i+1]) dp[i]=dp[i+1]+1;
    }
    int sum=0;
    for(int i=1;i<=n;i++) sum+=dp[i];
    printf("%d\n",sum);
    return 0;
}