Каждое утро Антон едет на работу на
автобусе.
Маршрут автобуса включает в себя n остановок, пронумерованных от 1 до n в порядке следования. Автобус
проезжает от каждой остановки до следующей за одну минуту, а его временем
стоянки можно пренебречь. Антон садится на первой остановке и выходит на
последней.
В автобусе есть m сидений, которые расположены в один ряд и пронумерованы от 1 до m, ближайшее к входу сиденье имеет номер
1, а самое дальнее – номер m. На
каждом сиденье может сидеть один пассажир, а также возле каждого сиденья может
стоять один пассажир. Когда человек входит в автобус, он садится на ближайшее
ко входу свободное сиденье. Если они все заняты, он ищет ближайшее ко входу
сиденье, рядом с которым никто не стоит, и встаёт у сидящего там человека над
душой. Если такого места нет, он выходит из автобуса.
Каждый пассажир остаётся на своём
месте до прибытия на нужную ему остановку. Стоящий пассажир остаётся стоять,
даже если какое-то сиденье освободилось.
На каждой остановке из автобуса
сначала выходят все пассажиры, которые собирались выйти на этой остановке, и
только потом заходят новые.
Антон зашёл в автобус первым, он
может сесть на любое сиденье и остаться на нём до конца поездки. Он хорошо
знает, кто ещё будет ехать в автобусе, про каждого пассажира Антон знает, на
какой остановке тот войдет в автобус и на какой выйдет. Помогите Антону выбрать
место так, чтобы во время поездки у него как можно меньше суммарно стояли над
душой.
Вход. В первой
строке входных данных заданы три целых числа n, m и k (2 ≤ n ≤ 109, 1 ≤ m ≤ 2 * 105, 0 ≤ k ≤ 2 * 105) –
количество остановок, количество сидений в автобусе и количество пассажиров,
кроме Антона.
В
следующих k строках задано по 2 числа
ai и bi, которые означают, что i-й пассажир собирается войти на ai-й остановке и выйти на bi-й (1 ≤ ai
< bi ≤ n).
Если на
одной остановке в автобус заходит несколько человек, они заходят в том порядке,
в котором они перечислены во входных данных.
Выход. Выведите
два числа на одной строке – минимальное суммарное время в минутах, в течение
которого у Антона будут стоять над душой, и номер места, на которое для этого
нужно сесть. Если таких мест несколько, выведите ближайшее ко входу.
|
Пример входа |
Пример выхода |
|
10 2 3 1 10 3 9 7 10 |
3 2 |
структуры данных +
моделирование
Количество
людей, стоящих у каждого из сидений, не зависит от начального выбора Антоном
места для сидения. Посадим Антона на любое (например первое) место.
Промоделируем езду в автобусе и найдем сидячее место, около которого меньше
всего суммарно по времени висели над душой. Туда и следует посадить Антона. Не
забываем, что пассажир может не войти в автобус, если он будет заполнен.
Реализация алгоритма
Количество свободных сидячих мест храним в переменной sit_cap. Номера свободных мест для
стояния содержатся во множестве stand.
int sit_cap;
set<int> stand;
Информацию о пассажирах храним в массиве v пар: первый
элемент пары содержит время входа или выхода пассажира, а второй – номер
(индекс) пассажира.
vector<pair<int,int> > v;
Следующие массивы служат для:
·
user_time[i] содержит время пребывания i-го пассажира в автобусе;
·
user_sit[i] содержит 1 или 0 в зависимости от
того сидит ли i-ый пассажир;
·
user_stand[i] содержит номер места, у которого
стоит пассажир номер i.
·
keep_user[i] содержит 1 или 0 в зависимости от
того зашел ли пассажир номер i в
автобус.
·
place_cap[i] содержит количество минут, суммарно в
течении которых стояли около места i;
vector<int> user_time,
user_sit, user_stand, keep_user, place_cap;
Основная часть программы. Читаем входные данные.
scanf("%d %d %d",&n,&m,&k);
Все места от 1 до m
являются свободными для стояния.
for(i = 1; i <= m; i++) // All stand places are free
stand.insert(i);
Инициализируем массивы. Имеются k пассажиров и m мест в
автобусе.
user_time.resize(k+1); user_sit.resize(k+1);
keep_user.assign(k+1,1);
place_cap.resize(m+1); user_stand.resize(k+1);
Читаем информацию о пассажирах. Если пассажир входит в
автобус, его номер заносим с положительным знаком, если выходит – с
отрицательным. Так мы будем различать события входа и выхода из автобуса.
user_time[i] содержит время пребывания i-го пассажира в автобусе.
for(i = 1; i <= k; i++)
{
scanf("%d %d",&a,&b);
v.push_back(make_pair(a,i)); // entrance
v.push_back(make_pair(b,-i)); // exit
user_time[i] = b - a;
// time user i in the bus
}
Сортируем события по времени.
sort(v.begin(),v.end());
Антон занимает одно из мест (неважно какое), имеем
сначала m – 1 свободное место.
sit_cap = m - 1;
Последовательно обрабатываем события входа / выхода из
автобуса.
for(i = 0; i < v.size(); i++)
{
Рассматриваем пассажира номер user.
int user = v[i].second;
Если пассажир входит в автобус, то user > 0.
if (user > 0) //
entrance
{
Если есть сидячие места то садим его на любое место,
обозначаем что пассажир номер user
сел (user_sit[user] = 1) и уменьшаем количество
свободных мест для сидения sit_cap на
1.
if (sit_cap > 0)
{
user_sit[user] =
1;
sit_cap--;
} else
Сидячих мест нет. Проверяем, есть ли стоячие места.
Если имеются, то наименьший номер места для стояния извлекаем из множества stand. user_stand[user]
содержит номер места, возле которого станет пассажир номер user.
if (!stand.empty())
{
user_stand[user]
= *stand.begin();
stand.erase(stand.begin());
}
else
Нет ни сидячих ни стоячих мест – автобус заполнен.
Пассажир номер user не смог
войти в автобус.
keep_user[user] =
0; // user can't enter the bus
}
else // exit
{
Обрабатываем выход из автобуса. Инвертируем номер
пассажира (user был отрицательным).
user = -user;
Если пассажир user
вошел в автобус, то обрабатываем его. Иначе пропускаем событие.
if(keep_user[user])
{
Если пассажир сидит, то он встает и уходит.
Освобождается одно сидячее место.
if (user_sit[user]) sit_cap++;
else
{
Пассажир номер user
стоит около места номер user_stand[user] и провел он около этого места
user_time[user] минут.
stand.insert(user_stand[user]);
place_cap[user_stand[user]] += user_time[user];
}
}
}
}
Ищем место pos,
возле которого меньше всего стояли. Ищем наименьшее значение в массиве place_cap и позицию pos в которой этот наименьший элемент находится.
int pos, min = n + 1;
for(i = 1; i <= m; i++)
if(place_cap[i] < min)
{
min =
place_cap[i];
pos = i;
}
Выводим ответ. На место pos следует
посадить Антона.
printf("%d %d\n",min,pos);