Мобильная версияПо сути, склады XXXX выстроены в круг, вы можете начать с любого склада, перемещаясь по часовой стрелке или против часовой стрелки, направление должно оставаться неизменным на протяжении всех оставшихся ходов.< /p>
На каждом складе хранятся определенные предметы. Цель состоит в том, чтобы собрать лишние товары с одних складов и доставить их другим, нуждающимся в них, чтобы в итоге на каждом складе хранилось одинаковое количество товаров (гарантировано).
Расстояние между 2 соседними складами равно 1, а Стоимость каждой транспортировки продукта — это расстояние, на которое перемещается продукт. Например, скажем, у нас есть 6->6->6->3->4 (связанные с первыми 6), мы можем оптимально начать с первых 6 и собрать 1 предмет, повторить то же самое для следующих 2 складов и доставить от 2 до 3 и от 1 до 4.
В итоге на каждом складе 5 товаров, а общая стоимость равна 1 + 2 + 3 + 1 = 7. Это всего лишь возможное движение по часовой стрелке, оптимальная стоимость должна учитывать также направление против часовой стрелки и возвращать минимальную стоимость. Я подумал, что это похоже на заправочную станцию LC 134, но не смог найти решение без использования грубой силы.
по сути
начинаем с 3, по часовой стрелке, [3, 4, 6, 6, 6]
начинаем с 4, по часовой стрелке, [4, 6, 6, 6, 3]
начните с 6, по часовой стрелке, [6, 6, 6, 3, 4]
начните с 6, против часовой стрелки, [6, 6, 6, 4, 3]
Код: Выделить всё
int getCost(const int n, const vector& a, const int target) {
int cost = 0, balance = 0, minBalance = 0;
for (const auto x : a) {
balance += x - target;
minBalance = min(minBalance, balance);
cost += balance;
}
return cost - minBalance * n;
}
int solve(vector& a) {
const int n = (int)a.size(), target = reduce(a.cbegin(), a.cend()) / n;
const int cw = getCost(n, a, target);
ranges::reverse(a);
const int ccw = getCost(n, a, target);
return min(cw, ccw);
}
int main() {
vector a {6,6,6,4,3};
cout
Подробнее здесь: [url]https://stackoverflow.com/questions/79074419/min-movement-to-move-products[/url]