Задача к ЕГЭ по информатике на тему «Передвижение по магистрали» №1

У медицинской компании есть $N$ пунктов приёма биоматериалов на анализ. Все пункты расположены вдоль автомагистрали и имеют номера, соответствующие расстоянию от нулевой отметки до конкретного пункта. Известно количество пробирок, которое ежедневно принимают в каждом из пунктов. Пробирки перевозят в специальных транспортировочных контейнерах вместимостью $V$ пробирок. Каждый транспортировочный контейнер упаковывается в пункте приёма и вскрывается только в лаборатории. Компания планирует открыть лабораторию в одном из пунктов. Стоимость перевозки биоматериалов равна произведению расстояния от пункта до лаборатории на количество контейнеров с пробирками. Общая стоимость перевозки за день равна сумме стоимостей перевозок из каждого пункта в лабораторию. Лабораторию расположили в одном из пунктов приёма биоматериалов таким образом, что общая стоимость доставки биоматериалов из всех пунктов минимальна. Определите минимальную общую стоимость доставки биоматериалов из всех пунктов приёма в лабораторию.

Входные данные:

Даны два входных файла — $A$ и $B$ , каждый из которых содержит в первой строке число $N$ ( $1 ≤ N ≤ 10000000$ ) – количество пунктов приёма биоматериалов, и число $V$ ( $1 ≤ V ≤ 1000$ ) – вместимость транспортировочного контейнера. Каждая из следующих $N$ строк содержит два натуральных числа: номер пункта и количество пробирок (не превышающее 10000). Пункты перечислены в произвольном порядке.

Пример входного файла:

6 96

5 4

7 3

1 100

10 190

2 200

8 2

При таких исходных данных (вместимость транспортировочного контейнера равна 96 пробирок) компании выгодно открыть лабораторию в пункте 2. В том случае сумма транспортных затрат составит $1⋅2+ 3 ⋅1+ 5⋅1 + 6⋅1+ 8 ⋅2 = 32$ . Ответ: 32.

Неэффективное решение

f = open(’27_A.txt’)
n, v = map(int, f.readline().split())
a = []
for i in range(n):
    s, k = map(int, f.readline().split())
    # кол-во сумок
    if k % v == 0:
        c = k//v
    else:
        c = k//v + 1
    a.append([s, c])
a.sort()

min_sum = 10**20
for i in range(n):
    new_sum = 0
    for j in range(n):
        new_sum += abs(a[i][0]-a[j][0])*a[j][1]
    min_sum = min(min_sum, new_sum)

print(min_sum)

Эффективное решение

f = open(’27_B.txt’)
n, v = map(int, f.readline().split())
a = []
for i in range(n):
    s, k = map(int, f.readline().split())
    # Считаем кол-во контейнеров
    if k % v == 0:
        c = k // v
    else:
        c = k // v + 1
    a.append([s, c])
a.sort()

# Стоимость доставки в нулевом пункте
s = 0
for j in range(n):
    s += abs(a[0][0] - a[j][0]) * a[j][1]

min_sum = s
left_sum = a[0][1] # Сумма пунктов слева, расстояние до которых увеличивается
right_sum = sum([x[1] for x in a]) - left_sum # Сумма пунктов справа, расстояние до которых уменьшается
for i in range(1, n):
    diff = a[i][0] - a[i - 1][0]  # Расстояние между двумя пунктами
    # Пересчет суммы:
    # для предыдущих пунктов дороже, для следующих дешевле
    s = s + diff * left_sum - diff * right_sum
    # Пересчет минимума
    min_sum = min(min_sum, s)
    left_sum += a[i][1]
    right_sum -= a[i][1]

print(min_sum)

Ответ: 128822 6201378713