Контест Junior Бинарный поиск спрашивают часто обновлено
Ближайший склад для каждого покупателя
Условие
На прямой стоят n складов и живут q покупателей. Каждого покупателя обслуживает ближайший к нему склад. Найдите суммарное расстояние от покупателей до их складов.
Ввод: в первой строке n и q (1 ≤ n, q ≤ 2500), во второй координаты складов, в третьей координаты покупателей. Все координаты целые от 0 до 10⁹, склады не обязательно упорядочены и могут совпадать.
Вывод: суммарное расстояние (может не поместиться в 32 бита).
Пример 1
Ввод:
3 4
10 1 5
0 4 7 12
Вывод:
6
Пример 2
Ввод:
1 1
5
5
Вывод:
0
Как подойти
Подсказки: 2
- Отсортируйте склады один раз.
- Ближайший склад: первый не левее покупателя или предыдущий перед ним.
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.