Начало
СоревнованияПодразделы
Другие разделы
Дата и время
19/12/2024 19:50:26
3. Трамвай
Сложная задача, необходимо использовать специальные структуры данных.
Фактически нужно промоделировать поездку трамвая. Когда пассажир входит в трамвай, если есть свободное место, и его `a_i-b_i\ >\ 0`, то он садится, иначе ищем среди сидящих пассажиров пассажира с минимальной разностью `a_i-b_i`. Если эта разность окажется меньше, чем у вошедшего, то этот пассажир должен уступить место вошедшему. Когда сидящий пассажир выходит из трамвая, то его место занимает пассажир с наибольшей положительной разностью `a_i-b_i` среди стоящих.
Для быстрого нахождения пассажира с минимальной разностью среди сидящих и максимальной разностью среди стоящих в C++ можно использовать класс STL set, который реализован на красно-черных деревьях. Реализовать эту структуру на Паскале очень сложно, но для данной задачи можно использовать гораздо более простое дерево сумм, которое позволяет находить `m`-ое по величине значение в наборе за логарифмическое время. Выглядит это дерево так:
В вершине с номером `k` хранится сумма значений в вершинах с номерами `2*k` и `2*k+1`. При изменении значений в листьях дерева в нижней строке, корректное состояние дерева восстанавливается за логарифмическое время.
Разность `a_i-b_i` не превышает `2\ 000\ 000` (отрицательные разности обрабатываются отдельно), поэтому храним дерево в массиве размером `4\ 194\ 303`, элементы с 1 по `2\ 097\ 151` хранят узлы дерева, а элементы с `2\ 097\ 152` по `4\ 194\ 303` – листья. Для обращения к нужному листу, хранящему количество пассажиров с некоторой разностью, нужно добавить к разности `2\ 097\ 152`
var sumtree:array[1..4194303] of longint;
...
k:=pass[j].a-pass[j].b+2097152;
if pass[j].c=i then
inc(sumtree[k]) { пассажир вошел }
else
dec(sumtree[k]); { пассажир вышел }
{ восстанавливаем корректность дерева }
while k>1 do
begin
k:=k div 2;
sumtree[k]:=sumtree[2*k]+sumtree[2*k+1];
end;
Для нахождения разности у `m`-го пассажира в отсортированном по разности наборе используем следующий код:
if sumtree[1] < m then
difm:=0 { пассажиров с положительной разностью меньше m }
else
begin
k:=1;
mm:=m;
while k<2097152 do
begin
k:=2*k+1; { переходим к правому потомку узла }
if sumtree[k]<mm then
begin { в правом потомке менее mm пассажиров }
mm:=mm-sumtree[k];
dec(k); { выбираем левого потомка }
end;
end;
difm:=k-2097152;
end;
После добавления или удаления пассажира проверяем как изменилась разность у `m`-го пассажира и изменяем сумму разностей сидящих пассажиров.
if pass[j].c=i then
begin { пассажир вошел }
if oldifm<pass[j].a-pass[j].b then { занял чье-то место }
sumd:=sumd+pass[j].a-pass[j].b-oldifm
end
else
begin { пассажир вышел }
if difm<pass[j].a-pass[j].b then { на его место кто-то сел }
sumd:=sumd-(pass[j].a-pass[j].b)+difm;
end;
oldifm:=difm;
Вместо написания быстрой сортировки пассажиров по номерам остановок, на которых они входят и выходят, можно сделать разделение пассажиров по спискам, соответствующим остановкам.
var
sl:array [1..100001] of integer; { номера первых пассажиров в спиcках }
pass:array [1..100000] of record
a,b,c,d:longint;
nextin,nextout:longint; { номер следующего в списке }
end;
...
{ Ввод и распределение по спискам }
readln(N,M,S);
for i:=1 to N do
begin
readln(pass[i].a,pass[i].b,pass[i].c,pass[i].d);
pass[i].nextin:=sl[pass[i].c];
sl[pass[i].c]:=i;
pass[i].nextout:=sl[pass[i].d];
sl[pass[i].d]:=i;
end;
Обработка списка для каждой остановки и вычисление результата выглядит так:
res:=0;
sumd:=0; { сумма разностей у сидящих }
sumb:=0; { сумма b[i] у всех пассажиров трамвая }
oldifm:=0;
for i:=1 to S do
begin
j:=sl[i]; { индекс первого пассажира,
вошедшего или вышедшего на i-ой остановке }
while j<>0 do { список не закончился }
begin
if pass[j].a>pass[j].b then
begin
{ модифицируем дерево сумм }
...
{ пересчитываем сумму разностей сидящих пассажиров }
...
end;
if pass[j].c=i then
begin { пассажир вошел }
sumb:=sumb+pass[j].b
j:=pass[j].nextin; { к следующему в списке }
end
else
begin { пассажир вышел }
sumb:=sumb-pass[j].b;
j:=pass[j].nextout; { к следующему в списке }
end;
end;
res:=res+sumd+sumb;
end;
writeln(res);
В операторе res:=res+(sumd+sumb); при сложении суммы разностей `a_i-b_i` для сидящих (sumd) и суммы `b_i` для всех пассажиров (sumb) получается сложение сумма `a_i` для сидящих и сумма `b_i` для стоящих.
