Ежедневная часть (e) C++ # 135, Распространенная проблема на собеседовании: конфеты для жадных детей.

Сегодня мы рассмотрим распространенную задачу на собеседованиях по C++: Candy для жадных детей.

Учитывая линию детей с разным уровнем жадности (представленную массивом целых чисел), определите минимальное количество конфет, которое вам нужно использовать, чтобы удовлетворить каждого ребенка.

Каждый ребенок должен получить хотя бы одну конфету, и каждый ребенок должен получить больше конфет, чем их менее жадные соседи.

Например, для ввода {1,3,5,2,99,99,1} минимальное количество конфет равно 12.

Прежде чем вы продолжите читать решение, я рекомендую вам попробовать решить его самостоятельно. Вот ссылка на Compiler Explorer с парой тестов: https://compiler-explorer.com/z/cc5369doa.

Решение

Давайте подумаем, как бы мы раздавали конфеты, если бы заботились только об одном направлении. Мы бы дали ребенку одну конфету, если он не более жадный, чем его единственный сосед, и сосед+1 конфету, если он более жадный.

К счастью, это напрямую приводит к решению. Если мы вычислим однонаправленные значения для обоих направлений, окончательное значение для каждого дочернего элемента будет просто max(left,right).

// Two-pass solution
int candy(const std::vector<int>& ratings) {
 // pre-calculate the right-to-left direction
 std::vector<int> reverse(ratings.size(), 1);
 for (ptrdiff_t i = std::ssize(ratings)-2; i >= 0; --i)
  if (ratings[i] > ratings[i+1])
   reverse[i] = reverse[i+1] + 1;

 int value = 1;
 int sum = reverse[0];
 // calculate the left-to-right direction & sum
 for (ptrdiff_t i = 1; i < std::ssize(ratings); ++i) {
  if (ratings[i] > ratings[i-1])
   ++value;
  else
   value = 1;
  sum += std::max(reverse[i], value);
 }
 return sum;
}

Откройте решение в Compiler Explorer.

Однако мы можем подсчитать количество конфет за один проход. Рассмотрим формы, которые мы формируем с помощью нашего решения. Самым жадным потомком будет вершина пика, имеющего левый склон, состоящий из 1,2,3…l и, аналогично, правый склон, состоящий из 1,2, 3…р. Итак, предположим, что мы считаем последовательные возрастающие и убывающие шаги. В этом случае мы можем рассчитать количество конфет как l*(l+1)/2 + r*(r+1)/2, при этом пик соединяется с более высоким наклоном, добавляя max(l,r)+1 конфеты.

// Single-pass solution
int candy_single_pass(const std::vector<int>& ratings) {
    if (ratings.size() <= 1)
        return ratings.size();

    // helpers
    constexpr auto count = [](int n) { return n*(n+1)/2; };
    enum Slope {
        UP,
        DOWN,
        NONE
    };
    constexpr auto slope = [](int l, int r) {
        if (l < r) return UP;
        if (l > r) return DOWN;
        return NONE;
    };  

    int sum = 0;
    int up = 0;
    int down = 0;
    Slope prev_slope = NONE;
    for (size_t i = 1; i < ratings.size(); ++i) {
        Slope new_slope = slope(ratings[i-1], ratings[i]);
        
        // End of peak
        if ((prev_slope == UP && new_slope == NONE) ||
            (prev_slope == DOWN && new_slope != DOWN)) {               
            // the greediest child adds std::max(up, down) + 1
            // but, each two peaks overlap on one child, so -1
            sum += count(up) + count(down) + std::max(up, down);
            up = 0;
            down = 0;
        }

        switch (new_slope) {
            case UP: ++up; break;
            case DOWN: ++down; break;
            // if there is no slope, there is no overlap between peaks
            case NONE: ++sum;
        }

        prev_slope = new_slope;
    }
    sum += count(up) + count(down) + std::max(up, down) + 1;
    return sum;
}

Откройте решение в Compiler Explorer.