Ежедневная часть (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.