Ежедневная часть (e) C++ # 205, Распространенная проблема на собеседовании: расщепление шариков.
Сегодня мы рассмотрим распространенную задачу интервью C++: расщепление шариков.
Дан ряд шариков с разными значениями, представленный как std::vector‹int64_t›, разделите эти шарики на k смежных секций.
Возвращает разницу между максимальным и минимальным достижимыми суммарными значениями разделов, учитывая, что раздел i..j имеет значение values[i]+values[j].
При достижимости O(n) предоставьте решение как минимум с O(n*logn).
Например, для мраморных значений {1,2,3,4,5} и трех разделов минимальное значение, которое мы можем получить, равно 14 с разделами { 1}, {2}, {3,4,5}, максимальное значение, которое мы можем получить, составляет 22 с разделами {1,2,3}, {4}, {5}.
Прежде чем вы продолжите читать решение, я рекомендую вам попробовать решить его самостоятельно. Вот ссылка на Compiler Explorer с парой тестов: https://compiler-explorer.com/z/a8s6YPh7M.
Решение
Эта проблема требует переосмысления. Что нас просят сделать?
Давайте рассмотрим общую сумму, которую мы пытаемся минимизировать и максимизировать. Это будут последовательности значений, которые всегда будут содержать values[0] и values[values.size()-1], а остальные элементы образуют соседние пары.
Поскольку перед нами стоит задача вернуть разницу, мы можем спокойно игнорировать граничные значения и сосредоточиться на соседних парах. У нас будет k-1 таких пар, и для минимума это будут k-1 пары с минимальными суммами, а для максимума это будут k-1 пары с максимальными суммами.
При этом мы можем переформулировать задачу: вернуть разницу между суммой k-1 самых низких смежных сумм и суммой k-1 наибольших смежных сумм. Это достижимо за O(n).
int64_t split_marbles(const std::vector<int64_t>& weights, int64_t k) { if (weights.size() < 2 || k < 2) return 0; // Generate the sums of adjacent elements auto sums_view = weights | std::views::pairwise_transform(std::plus<>{}); std::vector<int64_t> sums(sums_view.begin(), sums_view.end()); // Partition the sums, so that the following subrange represents // the lowest k-1 elements. std::ranges::nth_element(sums, sums.begin()+(k-2)); auto min_k = std::ranges::subrange(sums.begin(), sums.begin()+(k-2)+1); // The minimum sum is the total of these elements int64_t min = std::ranges::fold_left(min_k, int64_t{0}, std::plus<>{}); // Partition the sums, so that the following subrange represents // the largest k-1 elements. std::ranges::nth_element(sums, sums.end()-(k-1)); auto max_k = std::ranges::subrange(sums.end()-(k-1), sums.end()); // The maximum value is the total of these elements int64_t max = std::ranges::fold_left(max_k, int64_t{0}, std::plus<>{}); // Note, technically the actual min and max are both larger, // both also containing weights[0] and weights[weight.size()-1]. // Since we are taking a difference, it doesn't matter. return max-min; }
Откройте пример в Compiler Explorer.