Задание №27 — Оптимальный алгоритм для большого количества данных

#69239Задание №27ФИПИ

Анализ данных

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

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

Типовой пример организации данных во входном файле
6
1 100
2 200
5 4
7 3
8 2
10 190
При таких исходных данных и вместимости транспортировочного контейнера, составляющей 96 пробирок, компании выгодно открыть лабораторию в пункте 2. В этом случае сумма транспортных затрат составит: 1 ꞏ 2 + 3 ꞏ 1 + 5 ꞏ 1 + 6 ꞏ 1 + 8 ꞏ 2.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.
Предупреждение: для обработки файла B не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.

59136_27_A.txt

59136_27_B.txt

Правильный ответ

51063 5634689219329

Пояснение

Решение:

Из пункта с $t$ пробирками уезжает $w=\lceil t/36 \rceil$ контейнеров: контейнер вмещает не более 36 пробирок и вскрывается только в лаборатории, поэтому «недогруженный» контейнер всё равно нужен. В Python это удобно записать как -(-t // 36).

Если лабораторию открыть в пункте с номером $x_j$ , то стоимость доставки равна $C(j)=\sum_{i} w_i\,|x_i-x_j|.$ Перебирать все пункты и для каждого считать сумму — это $O(N^2)$ , для файла B слишком долго. Раскроем модуль: пункты слева от $j$ дают $x_j\sum_{i\lt j} w_i-\sum_{i\lt j} w_i x_i$ , пункты справа дают $\sum_{i\gt j} w_i x_i-x_j\sum_{i\gt j} w_i$ . Пункты в файле уже перечислены в порядке возрастания номера, поэтому, идя по ним слева направо и поддерживая четыре величины — $\sum w_i$ и $\sum w_i x_i$ слева и справа, — мы вычисляем $C(j)$ за $O(1)$ для каждого пункта, а весь ответ — за $O(N)$ .

def solve(name, cap=36):
    f = open(name)
    n = int(f.readline())
    x = [0] * n          # номера пунктов (они же расстояния от нулевой отметки)
    w = [0] * n          # число контейнеров в пункте
    for i in range(n):
        a, b = map(int, f.readline().split())
        x[i] = a
        w[i] = -(-b // cap)          # округление вверх: ceil(b / cap)
    wt = sum(w)
    xwt = sum(w[i] * x[i] for i in range(n))
    wl = 0               # сумма весов слева от текущего пункта
    xwl = 0              # сумма w*x слева от текущего пункта
    best = None
    for i in range(n):
        wr = wt - wl - w[i]
        xwr = xwt - xwl - w[i] * x[i]
        cost = x[i] * wl - xwl + xwr - x[i] * wr
        if best is None or cost < best:
            best = cost
        wl += w[i]
        xwl += w[i] * x[i]
    return best

print(solve('A.txt'), solve('B.txt'))

Проверка на примере из условия (вместимость 96): числа контейнеров равны

2,3,1,1,1,2

, минимум достигается в пункте 2 и равен

2+0+3+5+6+16=32

— совпадает с пояснением к заданию.Для файла A минимум равен

51\,063

(лаборатория в пункте

563

), для файла B —

5\,634\,689\,219\,329

.Ответ: 51063 5634689219329