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. 初始化一个 result 等大的数组。A 价值数组 1 糖果
2. 前向迭代数组并应用以下逻辑。
3. 向后迭代数组，并应用以下逻辑。
4. 计算下列各项的总和 result 阵列

第二步和第三步的逻辑。

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