Склад на сетке улиц
В городе улицы идут ровной сеткой — с запада на восток и с юга на север, — поэтому путь машины из точки (x1, y1) в точку (x2, y2) равен |x1 − x2| + |y1 − y2|. Сеть из n магазинов строит общий склад. К магазину i в точке (xi, yi) со склада каждый день выезжают wi машин. Склад можно поставить в любой точке с целыми координатами, хоть в одной точке с магазином. Найдите наименьший возможный суммарный путь всех машин за день: Σ wi · (|x − xi| + |y − yi|).
Один из закрытых тестов — настоящий: 675 населённых пунктов одного края по данным GeoNames на сетке с шагом 100 м, с числом жителей в роли wi.
Вход
В первой строке n (1 ≤ n ≤ 100 000). Дальше n строк по три целых числа: xi, yi (|xi|, |yi| ≤ 106) и wi (1 ≤ wi ≤ 106). Магазины могут стоять в одной точке.
Выход
Одно число — наименьший суммарный путь.
Примеры
Пример 1
3 0 0 1 4 0 1 10 6 1
16
Пример 2
4 0 0 3 2 1 1 9 9 1 10 10 1
41
Ограничения
- Время · Python
- 4000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 11 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Сумма |x − xi| + |y − yi| распадается на две: одна зависит только от x, другая — только от y. Значит, хватит решить задачу на прямой: где поставить точку, чтобы сумма взвешенных расстояний до точек на прямой была наименьшей?
2Подсказка 2
Сдвиньте склад на прямой на единицу вправо. Как изменится сумма? Все машины, которые ехали влево, проедут на единицу больше, а все, что ехали вправо, — на единицу меньше.
3Идея
Пусть слева от склада (и в нём самом) магазины с суммарным весом L, справа — с весом R. Шаг вправо меняет сумму на L − R: пока справа веса больше половины, идти вправо выгодно, когда слева набралось не меньше половины, — уже нет. Оптимум там, где накопленный слева вес впервые достигает половины всего веса. Это взвешенная медиана — обычная медиана, если все веса равны.
Центр масс — взвешенное среднее — здесь не годится: он минимизирует сумму квадратов расстояний, а не самих расстояний. Один далёкий магазин с большим весом тянет среднее к себе, а медиану сдвигает не дальше соседнего магазина.
4Разбор
Для каждой оси отдельно: сортируем точки по координате, идём слева направо с накопленным весом и останавливаемся на первой точке, где удвоенный накопленный вес стал не меньше общего. Координата этой точки — оптимальная координата склада. Если накопленный вес ровно равен половине, оптимальна любая точка до следующего магазина — сумма на всём этом отрезке одинакова, поэтому ответ от выбора не зависит. Осталось сложить взвешенные расстояния.
Сортировка не обязательна. Взвешенную медиану ищет и быстрый выбор: разбиваем точки вокруг опорной, складываем веса левой части и идём туда, где лежит половина общего веса, — в среднем O(n). На 100 000 точках разницы не видно, но на миллиардах записей в аналитике медианы ищут именно так или приближённо.
В первом примере у трёх магазинов веса равны, и склад встаёт в медиану по каждой оси: x = 4, y = 0, путь — 16. Центр масс (4,67; 2) после округления дал бы 19.
4+Решение
5Сложность
Сортировка двух осей — O(n log n), с быстрым выбором — O(n) в среднем. Сумма доходит до 105 · 106 · 4 · 106 = 4 · 1017 и помещается в 64-битное целое; в Python целые и так без предела.
6Типичные ошибки
- Центр масс. Самое частое решение «в лоб»: взвешенное среднее координат. Оно минимизирует не ту сумму. Тест с одним далёким магазином в миллион машин показывает разницу ярче всего.
- Медиана без весов. Медиана координат магазинов, где каждый магазин считается один раз, верна только при равных весах.
- Медиана по расстоянию до центра. Задача на сетке распадается по осям; искать «центральный» магазин по евклидову расстоянию — другая задача.