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. Инициализировать массив result равного размера как массив A со значением 1 для каждой позиции (каждый дочерний элемент получает по крайней мере одну конфету)
2. Вперед перебирать массивы и применять следующие logi c
3. Выполнить итерацию в обратном направлении по массивам и применить следующие logi c
4. Вычислить сумму result массива

Logi c для шагов 2 и 3:

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