Ежедневный бит (е) C ++ # 77, Общие проблемы на собеседованиях: минимальная стоимость для достижения равного массива
Сегодня мы рассмотрим распространенную задачу интервью C++: минимальная стоимость достижения равного массива.
Имея два массива (числа и стоимости) положительных целых чисел, определите минимальную стоимость корректировки массива чисел таким образом, чтобы все элементы имели одинаковое значение.
Стоимость корректировки каждого элемента на единицу равна соответствующему элементу в массиве затрат.
Например, для массива чисел {1,3,5,2} и массива затрат {2,3,1,14} результат равен 8. Самый дешевый целевой массив – {2,2,2,2}, это означает, что нам придется скорректировать элементы 1 и 3 один раз стоимостью 1*2+1*3 и элемент 5 три раза стоимостью 3*1, всего 8.
Прежде чем вы продолжите читать решение, я рекомендую вам попробовать решить его самостоятельно. Вот ссылка на Compiler Explorer с парой тестов: https://compiler-explorer.com/z/dedx8Yd68.
Решение
Чтобы решить эту задачу, нам понадобится немного математических знаний.
Давайте сначала рассмотрим один элемент массива. Функция, представляющая стоимость корректировки этого элемента, выпукла; то есть минимум функции - это когда мы вообще не настраиваем этот элемент и далее монотонно растет в обе стороны.
Математическая мелочь состоит в том, что сумма выпуклых функций также выпукла.
Мы можем использовать бинарный поиск, чтобы найти минимум выпуклой функции. В данном случае функция представляет собой общую стоимость, которую мы (из-за бинарного поиска) вычислим в общей сложности logk раз, где k — область значений в массиве чисел (т. е. max(числа)-min(числа)). Поскольку наша функция стоимости представляет собой простое линейное сокращение, мы получаем общую сложность O(n*logk).
#include <vector>
#include <algorithm>
#include <numeric>
#include <cstdint>
int64_t cost(const std::vector<unsigned>& nums,
const std::vector<unsigned>& costs,
unsigned target) {
return std::inner_product(nums.begin(), nums.end(),
costs.begin(),
0LL,
std::plus<>{},
[target](int64_t num, int64_t cost) {
return std::abs(num-target)*cost;
});
}
int64_t minimum_cost(const std::vector<unsigned>& nums,
const std::vector<unsigned>& costs) {
int64_t best = cost(nums, costs, nums[0]);
// It only makes sense to search within the bounds
// of the existing values
auto [left,right] = std::ranges::minmax(nums);
// Standard binary search
while (left < right) {
auto mid = (left + right)/2;
auto cost_mid = cost(nums, costs, mid);
// However, since we are searching on a convex function
// we have to check on which side from the minimum we are
auto cost_right = cost(nums, costs, mid+1);
best = std::min(cost_mid, cost_right);
// Mid is on the left side from the minimum
// and can't be the minimum
if (cost_mid > cost_right)
left = mid + 1;
// Mid is on the right side of the minimum
// and can be the minimum
else
right = mid;
}
return best;
}
