7029. Поликлиника

На прием к доктору каждый день приходит много людей. Каждый пациент находится на приеме целое число минут, однако разных пациентов доктор может принимать разное количество времени. Доктор начинает прием в момент времени t₁ минут и заканчивает прием в момент времени t₂ минут. Это означает, что любой пациент независимо от того, сколько времени его будет принимать доктор, может зайти на прием в моменты t₁, t₁ + 1, …, t₂ − 1. Заходить на прием к доктору в другое время или тогда, когда доктор принимает другого пациента, запрещено. Если пациент приходит в поликлинику в момент t, он ожидает первый момент времени s ≥ t такой, что на этот момент доктор ведет прием, причем уже успел осмотреть всех пациентов, которые пришли в поликлинику раньше, то есть до момента t. Если доктор не успевает осмотреть всех до конца приема, то остаток пациентов должен прийти на следующий день.

Зная, в какой момент доктор начинает и заканчивает прием, те, кто и когда придут на прием в конкретный день, а также сколько времени будет осматривать доктор каждого пациента, определите момент времени, в который необходимо прийти на прием Пете Пяточкину, чтобы гарантированно попасть в этот день к доктору, и при этом ожидать приема как можно меньше. В случае, если имеется несколько альтернативных вариантов такого момента времени, Вам необходимо определить наименьший (наиболее ранний) из них.

Вход. В первой строке приведено три числа: количество желающих попасть на прием n, время начала приема t₁ и время завершения приема t₂, больший чем t₁.

Во второй строке перечислены n чисел a₁, a₂, …, a_n – время, когда в поликлинику зашли соответственно первый, второй, …, n-ый желающий попасть к доктору. Числа a₁, a₂, …, a_n попарно различны и расположены в порядке возрастания.

В третьей строке перечислены n чисел b₁, b₂, …, b_n – время, необходимое доктору на осмотр соответственно первого, второго, …, n-го пациента.

Все входные числа натуральные. Количество пациентов n не больше 10⁵, остальные числа не превосходят 10⁹.

Сутки на планете, где проживает Петя Пяточкин, длятся значительно дольше, чем на Земле, поэтому время начала приема t₁, время завершения приема t₂, а также числа a₁, a₂, …, a_n и b₁, b₂, …, b_n могут быть большими чем 1440 – количество минут в земных сутках.

Выход. Вывести наименьший момент времени, когда Петя Пяточкин должен прийти в поликлинику, чтобы гарантированно попасть к доктору, подождав приема как можно меньше времени. Если Петя придет одновременно с другим человеком, его как младшего пропустят вперед.

Пример входа	Пример выхода
5 10 20 4 9 12 16 22 4 10 10 9 2	9

РЕШЕНИЕ

жадные алгоритмы

Анализ алгоритма

Если до момента времени t₁ посетителей не было, то Петя Пяточкин может прийти к доктору в t₁. Вычислим для каждого больного время его попадания s_i к врачу. Если для некоторого i имеет место неравенство s_i + b_i ≤ a_i+1, то Петя может прийти в момент времени s_i + b_i, попав сразу к врачу без ожидания. В противном случае Пете придется ждать. Причем если он придет в момент a_i, то ждать придется s_i – a_i минут. Находим i, для которого указанная разность минимальна.

Реализация алгоритма

Массив а содержит время прихода пациентов в поликлинику, массив b время приема пациентов доктором. s[i] содержит время, когда i-ый пациент сможет попасть на прием к доктору.

#define MAX 100002

int a[MAX], b[MAX], s[MAX];

Читаем входные данные.

scanf("%d %d %d",&n,&t1,&t2);

for(i = 1; i <= n; i++)

scanf("%d",&a[i]);

for(i = 1; i <= n; i++)

scanf("%d",&b[i]);

Если первый пациент приходит в поликлинику не раньше времени t₁, когда доктор начинает прием, то Петя может прийти во время t₁ и сразу попасть к врачу.

if (a[1] >= t1)

{

printf("%d\n",t1); return 0;

}

Первый пациент сможет попасть к доктору в момент времени t₁.

s[1] = t1; a[n+1] = t2;

for(i = 1; i <= n; i++)

{

Если осмотр i-го пациента закончится после окончания времени приема доктора t₁, то (i + 1) - ый пациент уже на прием попасть не сможет.

if (s[i] + b[i] >= t2) break;

Если в момент времени s[i] + b[i] в очереди никого нет (только что закончился осмотр i-го пациента), то Петя может прийти в этот момент в поликлинику и сразу попасть к врачу (ожидать ему не придется ни минуты).

if (s[i] + b[i] <= a[i+1])

{

printf("%d\n",s[i] + b[i]);

return 0;

}

(i + 1) - ый пациент уже стоит в очереди (он пришел раньше времени s[i] + b[i]), но только сейчас может попасть на прием.

s[i+1] = s[i] + b[i];

}

Пете есть смысл приходить в поликлинику вместе с некоторым посетителем, то есть в некоторый момент времени a_i. При этом ждать ему придется s[i] – a[i] минут. Ищем i, для которого эта разность принимает наименьшее значение.

for(min = 0x3FFFFFFF, i = 1; s[i] && (i <= n); i++)

if (s[i] - a[i] < min)

{

min = s[i] - a[i];

t = a[i];

}

Выводим наименьший момент времени t, когда Петя Пяточкин должен прийти в поликлинику.

printf("%d\n",t);