Задача
На прием к доктору каждый день приходит много людей. Каждый пациент находится на приеме целое число минут, однако разных пациентов доктор может принимать разное количество времени. Доктор начинает прием в момент времени $t_1$ минут и заканчивает прием в момент времени $t_2$ минут. Это означает, что любой пациент независимо от того, сколько времени его будет принимать доктор, может зайти на прием в моменты $t_1, t_1 + 1, …, t_2 − 1$. Заходить на прием к доктору в другое время или тогда, когда доктор принимает другого пациента, запрещено. Если пациент приходит в поликлинику в момент $t$, он ожидает первый момент времени $s ≥ t$ такой, что на этот момент доктор ведет прием, причем уже успел осмотреть всех пациентов, которые пришли в поликлинику раньше, то есть до момента $t$. Если доктор не успевает осмотреть всех до конца приема, то остаток пациентов должен прийти на следующий день.
Зная, в какой момент доктор начинает и заканчивает прием, те, кто и когда придут на прием в конкретный день, а также сколько времени будет осматривать доктор каждого пациента, определите момент времени, в который необходимо прийти на прием Пете Пяточкину, чтобы гарантированно попасть в этот день к доктору, и при этом ожидать приема как можно меньше. В случае, если имеется несколько альтернативных вариантов такого момента времени, Вам необходимо определить наименьший (наиболее ранний) из них.
Входные данные
В первой строке приведено три числа: количество желающих попасть на прием n, время начала приема $t_1$ и время завершения приема $t_2$, больший чем $t_1$.
Во второй строке перечислены $n$ чисел $a_1, a_2, …, a_n$ — время, когда в поликлинику зашли соответственно первый, второй, $…, n$-ый желающий попасть к доктору. Числа $a_1, a_2, …, a_n$ попарно различны и расположены в порядке возрастания.
В третьей строке перечислены n чисел $b_1, b_2, …, b_n$ — время, необходимое доктору на осмотр соответственно первого, второго, $…, n$-го пациента.
Все входные числа натуральные. Количество пациентов $n$ не больше $10^5$, остальные числа не превосходят $10^9$.
Сутки на планете, где проживает Петя Пяточкин, длятся значительно дольше, чем на Земле, поэтому время начала приема $t_1$, время завершения приема $t_2$, а также числа $a_1, a_2, …, a_n$ и $b_1, b_2, …, b_n$ могут быть большими чем 1440 — количество минут в земных сутках.
Выходные данные
Вывести наименьший момент времени, когда Петя Пяточкин должен прийти в поликлинику, чтобы гарантированно попасть к доктору, подождав приема как можно меньше времени. Если Петя придет одновременно с другим человеком, его как младшего пропустят вперед.
Тесты
| № | Входные данные | Выходные данные |
| 1 | 3 10 20 7 14 18 5 2 1 |
17 |
| 2 | 5 10 20 4 9 12 16 22 4 10 10 9 2 |
9 |
| 3 | 1 10 20 5 15 |
5 |
Код
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
#include <iostream> using namespace std; int a[100003], b[100003]; int main() { long long t1, t2, t, n, i, j, l; cin >> n >> t1 >> t2; t = 0; //Заполняем время прихода пациентов на приём в массив a for (i = 1; i <= n; i++) { cin >> a[i]; } //Заполняем время на приём пациентов в массив b for (i = 1; i <= n; i++) { cin >> b[i]; } //Проверяет приходит ли пациент в начале времени приёма или после его начала if (a[1] >= t1) { cout << t1 << endl; return 0; } //Вводим точки отсчёта else { t = a[1]; l = t1 - a[1]; t1 += b[1]; } j = 2; //Условие: Если разница между началом приёма и приёмом > 0; цикл не прошёл всех пациентов; приём ещё не окончен. while (l > 0 && j <= n && t1 < t2) { //Проверяет приходит ли следующий пациент к началу или уже после начала приёма врача if (a[j] >= t1) { t = t1; l = 0; } else { //Проверяет является ли разница между началом приёма следующего пациента и временем его прихода меньше, чем предыдущая зафиксированная разница if (t1 - a[j] < l) { t = a[j]; l = t1 - a[j]; } t1 += b[j]; } j++; } //Если время приёма ещё не окончено, пациенты все прошли и прийти раньше не получилось - приходим сразу в конце приёма последнего if (t1 < t2 && l != 0 && j > n) { t = t1; l = 0; } cout << t << endl; } |
Решение
Создаём два массива, удовлетворяющих условия, a — время прихода пациентов и b — время на их приём. Инициализируем все необходимые переменные: t_1 и t_2 — время приёма, t — время в которое Петя должен прийти, n- кол-во пациентов, i и j — счётчики, l — время между приходом пациента и началом его приёма.
Проверяем приходит ли первый пациент в самое начало приёма или после начала приёма, если в начало приёма — то приходим тогда.
В цикле while определяем минимальное время, в которое Петя может прийти на приём к врачу. Проверяем приходит ли следующий пациент до завершения приёма предыдущего. Если приходит во время завершения, или через некоторое время, то заходим после приёма предыдущего. (Нам уступают) Если нет, цикл продолжается, проверяет, является ли разница между началом приёма следующего пациента и временем его прихода меньше, чем предыдущая зафиксированная разницы. Если да — записывает её и время прихода данного пациента, и переходит к следующему пациенту.
В конце проверяем, если время приёма ещё не окончено, пациенты все прошли и прийти раньше не получилось — приходим сразу в конце приёма последнего.