1.题目描述
有 N 个孩子站成一排，每个孩子有一个分值。给这些孩子派发糖果，需要满足如下需求：
1、每个孩子至少分到一个糖果
2、分值更高的孩子比他相邻位的孩子获得更多的糖果
求至少需要分发多少糖果？
- 输入描述:
0,1,0 - 输出描述:
4 - 输入示例:
5,4,1,1 - 输出示例:
7
2.题目解析
注意顺序不能变。
本题关键在于分析并实现程序逻辑。派分糖果主要存在以下几种情况。
一般规则：
- 当前分值与前一分值相等，分到糖果数也与前一相邻位的孩子相同。
- 当前分值大于前一分值，分到糖果数比前一相邻位的孩子多1颗。
- 当前分值小于前一分值，分到糖果数比前一相邻位的孩子少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()));
}
