Задача 68: Автобус (XIII Всеукраинская олимпиада по информатике)
Служебный автобус совершает один рейс
по установленному маршруту и в случае наличия свободных мест
подбирает рабочих, которые ожидают на остановках, и отвозит их на
завод. Автобус также может ждать на остановке рабочих, которые еще
не пришли. Известно время прихода каждого рабочего на свою остановку
и время проезда автобуса от каждой остановки до следующей. Автобус
приходит на первую остановку в нулевой момент времени.
Продолжительность посадки рабочих в автобус считается нулевой.
Задание: Написать программу BUS, которая определит
минимальное время, за которое автобус привезет максимально возможное
количество рабочих.
Входные данные: Входной текстовый файл BUS.DAT в первой
строке содержит количество остановок N и количество мест в автобусе
M. Каждая i-я строчка из последующих N строчек содержит целое число
- время движения от остановки _ к остановке i+1 (N+1-я остановка -
завод), количество рабочих K, которые придут на i-ю остановку, и
время прихода каждого рабочего на эту остановку в порядке прихода (1
<= M <= 2000, 1 <= N,K <= 200000).
Пример входных данных.
3 5
1 2 0 1
1 1 2
1 4 0 2 3 4
Выходные данные: Единственная строка выходного текстового
файла BUS.SOL должен содержать минимальное время, необходимое для
перевозки максимального количества рабочих.
Пример выходных данных.
4
Решение:
Мой насморк вроде бы прекратился (на спрее было написано, что надо
брызгать 2 раза в каждую ноздрю 2 раза в день, а я брызгал по 6-8
раз 4-5 раз в день).
Теперь, собственно, решение. Сначала определим, что такое
максимально возможное количество рабочих. Если общее количество
рабочих больше вместимости автобуса, то это - объем автобуса, если
же рабочих меньше чем вместимость автобуса - то это количество всех
рабочих (в этом случае вместимости автобуса уместно присвоить
значение, равное количеству людей).
Задачу надо решать с помощью двоичного поиска (бинарного поиска,
дихотомии). А лучше с помощью двух двоичных поисков.
Когда мы считываем данные, следует определить время прихода
последнего человека (т.е. то время, когда уже все люди будут на
остановках) - это будет максимум в двоичном поиске. Минимум будет
равен нулю. Если автобус должен задержаться перед остановкой, то он
должен сделать это перед первой остановкой (действительно, если он
подъедет к первой остановке, заберет людей, а потом будет ждать у
второй остановки, то в это время на первую могут придти еще люди, а
если ждать перед первой, то люди со второй никуда не денутся).
Минимум и максимум у нас есть. Теперь берем задержку, равную x = (min
+ max) / 2. С помощью процедуры, которая будет описана ниже,
вычисляем, сколько людей успеет придти до момента x на первую
остановку, для второй остановки будет задержка, равная x + a[1], где
a[1] - время следования от первой остановки до второй, для третьей
задержка - x + a[1] + a[2] и т.д. Если количество севших в автобус
на всех остановках больше либо равно вместимости автобуса, то надо
заменить x на (min + x) / 2, если остались места в автобусе то x = (x
+ max) / 2. Условие выхода будет такое: если при некоторой задержке
x автобус заполнен, а при задержке (x - 1) автобус не полон, то
ответ x.
Теперь вторая дихотомия. Та самая, которая определяет, сколько людей
успеет придти на определенную остановку до определенного момента.
Здесь максимумом дихотомии будет количество людей на остановке, а
минимумом - ноль. Выбираем среднего человека - если его время
прихода меньше, чем задержка, то x = (x + max) / 2, если он не
успеет придти, то x = (min + x) / 2. Здесь условие выхода такое:
если человек успевает придти на остановку, а следующий за ним нет -
то ответом будет номер человека. Отдельно нужно обрабатывать случай,
если на автобус сядут все люди с остановки.
Далее
ð
