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