Distirbute Candy - 查找问题的最小可重现示例

Question

问题是给N个孩子分发糖果。每个孩子都有一个评分。分配应该使每个孩子至少有一个糖果，评分较高的孩子比邻居得到更多的糖果。查找此类分发的最小糖果数量。

方法：

iterate each child.
if (rating of curr child < rating of next child)
add to total and increase candy
else if (rating of curr child equal to rating of next child)
we can bring down candy for next child to 1
else if ( rating of curr child > rating of next child)
{     // if child ratings are {4 3 2 5} then 
//optimal is {3 2 1 2}
//the detailed code is below
}

详细代码为：

int n = A.size();
int count  = 0;
int step = 1;
int i = 0;
bool run = true;
while(run){
if(i+1 ==n){
count+=step;
run = false;
}
else if(A[i+1] > A[i]){
count+=step;
step++;
i+=1;;
}else if(A[i+1] == A[i]){
count+=step;
step = 1;

i+=1;
}else {
int j = i;
while(A[i+1] < A[i]&& (i+1)<n){
i+=1;
}

int x = i-j;
step = max(step,x+1);
count+=step;
count+=((x*(x+1))/2);
step = 2;
if(i==n-1)
run = false;
i+=1;

}
}

return count;

代码不会生成预期的输出。由于测试用例很大，我无法确定错误原因。有人可以提供它中断的示例测试用例吗？

失败的测试用例附在下面的链接中。第一个数字表示数组的大小。 中断测试用例

Answer 1

如果只需要一个在代码中公开错误的示例，请使用3 2 2并停止读取。

---

我会建议一个非常字面的问题解决方案：

1. 初始化一个大小与A数组大小相等的result数组，每个位置的值为1(每个孩子至少得到一个糖果(
2. 前向迭代数组并应用以下逻辑
3. 向后迭代数组并应用以下逻辑
4. 计算result数组的总和

步骤 2 和 3 的逻辑：

if (A[current] > A[previous] && result[current] <= result[previous])
result[current] = result[previous] + 1;

Answer 2

迭代每个子项。 如果(当前孩子的评级<下一个孩子的评级(>下一个孩子的评级( {//如果子评级为 {4 3 2 5}，则 最优为 {3 2 1 2} 详细