1.题目描述

有 N 个孩子站成一排，每个孩子有一个分值。给这些孩子派发糖果，需要满足如下需求：
1、每个孩子至少分到一个糖果
2、分值更高的孩子比他相邻位的孩子获得更多的糖果
求至少需要分发多少糖果？

• 输入描述:

  0,1,0
  

• 输出描述:

  4
  

• 输入示例:

  5,4,1,1
  

• 输出示例:

  7
  

2.题目解析

注意顺序不能变。
本题关键在于分析并实现程序逻辑。派分糖果主要存在以下几种情况。
一般规则：

1. 当前分值与前一分值相等，分到糖果数也与前一相邻位的孩子相同。
2. 当前分值大于前一分值，分到糖果数比前一相邻位的孩子多1颗。
3. 当前分值小于前一分值，分到糖果数比前一相邻位的孩子少1颗。
   潜在规则：
   当前分值小于前一分值，分到糖果数比前一相邻位的孩子少1颗，但是糖果不能少于1颗，当少于1颗时，前面的要增加糖果数量。
   例如：6,5,5,5,4,1,1

3.参考答案

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n = 5;
    // int nums[n] = {1,2,3,5,2,1};
    // int nums[n] = {1,2,3,5,2,2,1,2};
    // int nums[n] = {1,2,3,5,4,3,2,2,1,2};
    // int nums[n] = {5,4,3,2,1};
    // int nums[n] = {5,5,5,5,5};
    // int nums[n] = {1,2,3,4,5};
    // int nums[n] = {1,2,4,9,15};
    int sugers[n];
    sugers[0] = 1;
    for(int i=1;i<n;++i){
        if(nums[i-1] == nums[i]){ // 相邻孩子分值相等
            sugers[i] = sugers[i-1];
        }else if(nums[i-1] < nums[i]){ // 后一个孩子分值大于前一个孩子
            sugers[i] = sugers[i-1] + 1;
        }else{// 后一个孩子分值小于前一个孩子
            sugers[i] = 1;
            int now = i;
            int pre = now - 1;
            //  后一个孩子分值小于前一个孩子,不发糖果
            while(pre >=0 && nums[pre] >= nums[now] && sugers[pre] <= sugers[now]){
                ++sugers[pre];
                --now;
                --pre;
            }
        }
    }
    int res = 0;
    for(int i=0;i<n;++i){
        res += sugers[i];
    }
    printf("\n%d\n",res);
}

#include <bits/stdc++.h>
using namespace std;
int solve(int* nums,int n){
  int counts[n]; // 存放每个小孩分配糖果数
  fill_n(counts,n,0); // 结果清零
  counts[0] = 1;

  for(int i=1;i!=n;++i){// 遍历所有分值
    if (nums[i] == nums[i-1]){ // 分值相等糖果相等
      counts[i] = counts[i-1];
    } else if (nums[i] > nums[i-1]){ // 当前学生比前一个学生分值高，多分1个糖果
      counts[i] = counts[i-1]+1;
    } else { // 当前学生比前一个学生分值低
      if(counts[i-1]>1){ // 前一个学生糖果数多于1
        counts[i] = counts[i-1]-1; // 当前学生比前一个学生糖果数少1
      }else{ // 如果前一个学生糖果数为1
        counts[i] = 1;// 当前学生糖果数为1
        for(int j = i;j>=1;--j){// 把前面连续高分数的学生糖果都加1
          if(nums[j-1] < nums[j]) break; // 直到遇到分数低的学生为止
          if(nums[j-1] >= nums[j]) ++counts[j-1];
        }
      }
    }

    // 用于查看过程
    // for_each(counts,counts+n,[](int n){cout<<n<<" ";});
    // cout << endl;
  }
  // 统计所有的糖果
  return accumulate(counts,counts+n,0);
}
int main(){
  vector<int> nums;
  int num = 0;
  while(cin>>num){
    nums.push_back(num);
    char c = cin.peek(); // 获取下个字符
    if('\n' == c) break; // 回车表示输入结束
    cin.ignore(1,','); // 除去逗号分割符
  }
  printf("%d\n",solve(nums.data(),nums.size()));
}