分发糖果 - 寻找问题的最小可重现示例

Question

题目是给N个发糖果children.Eachchild有评分。分配应该是这样的，每个 child 至少有一个糖果，并且评分较高的 children 比他们的邻居得到更多的糖果。找到这种分配的最小糖果数量。

方法：

  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;

代码没有产生预期的输出。由于测试用例庞大，我无法确定错误原因。有人可以提供示例测试用例吗？

下面附上失败的测试用例link。第一个数字表示数组的大小。 Breaking test case

Answer 1

如果您只需要一个暴露代码错误的示例，请使用 3 2 2 并停止阅读。

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

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

第 2 步和第 3 步的逻辑：

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

Answer 2

迭代每个 child。如果（当前评分 child < 下一个评分 child）添加到总数并增加糖果 else if（当前 child 的评分等于下一个 child 的评分）我们可以将下一个 child 的糖果降为 1 else if ( 当前评分 child > 下一个评分 child) { // 如果 child 评分是 {4 3 2 5} 那么 //最优是{3 2 1 2} //详细

分发糖果 - 寻找问题的最小可重现示例

Distirbute Candy - Finding minimum reproducible example of the problem

c++

arrays

algorithm

data-structures

greedy

方法：