Задача 6413. Источник: Поляков. Задание КИМ 26
(Д. Муфаззалов) На парковке расположены парковочные места для M категорий автомобилей. Номер категории – целое неотрицательное число, меньшее, чем M. Для каждой категории автомобилей выделено некоторое количество парковочных мест. Приезжающий на парковку автомобиль занимает любое свободное место среди мест, предназначенных для автомобилей его категории, а также среди мест, предназначенных для автомобилей c бóльшим номером категории. Автомобиль всегда паркуется на подходящем свободном месте для автомобилей с наименьшей категорией. Если подходящего свободного места нет, автомобиль уезжает. Гарантируется, что никакие два автомобиля не приезжают одновременно. Если время прибытия автомобиля совпадает со временем окончания стоянки другого автомобиля, вновь прибывший автомобиль может занять освободившееся место, если оно подходит ему.
Пусть K – минимальный номер категории парковочных мест, в которой за всё время припарковалось наибольшее количество автомобилей. Определите время, через которое освободятся (и больше не будут заняты) все парковочные места категории K, и количество автомобилей, которые парковались на местах категории K.
Входные данные представлены в файле 26-120.txt следующим образом. Первая строка входного файла содержит два натуральных числа, записанных через пробел: M – количество категорий автомобилей, 1 ≤ M < 525 600, и N – общее количество автомобилей, приехавших на парковку в течение одного года, 0 ≤ N ≤ 106. Вторая строка содержит M чисел – количество парковочных мест на стоянке для автомобилей каждой категории, начиная с категории под номером 0, в порядке возрастания номеров категорий. Каждое из этих чисел не превышает 1000. Каждая из N последующих строк описывает один автомобиль и содержит три целых числа: время в минутах с начала года, когда автомобиль прибыл на парковку; необходимую длительность стоянки в минутах и номер категории автомобиля.
В ответе запишите два целых числа: время освобождения парковочных мест категории K, затем – общее количество автомобилей, которые парковались на местах категории K.
Пример входного файла:
2 5
2 1
5 22 0
8 30 1
14 15 0
25 12 0
20 40 1
При таких исходных данных: 1-й автомобиль (категории 0) припаркуется на месте категории 0 с 5 по 27 минуты, 2-й автомобиль (категории 1) припаркуется на месте категории 1 с 8 по 38 минуты, 3-й автомобиль (категории 0) припаркуется на месте категории 0 с 14 по 29 минуты, 4-й автомобиль (категории 0) не найдет место, 5-й автомобиль (категории 1) не найдет место. В категории мест с номером 0 припарковалось максимальное количество автомобилей – 2, все парковочные места категории 0 освободились на 29-й минуте. Ответ: 29 2.
Решение
Отсортируем исходные данные в двухмерном массиве a по времени прибытия на парковку (в программах на PascalABC и C++ использован алгоритм сортировки выбором). Последовательно обрабатывая информацию об автомобилях, будем выбирать наименьшую подходящую категорию и помещать информацию о времени освобождения парковочного места в двухмерный массив b, где первым элементом является время освобождения, а вторым - категория места. Переменная nb хранит фактическое количество данных в массиве. Перед помещением каждого нового автомобиля в массив b, будем удалять из него все автомобили, которые должны были покинуть парковку к прибытию обрабатываемого автомобиля. В данном решении массив b отсортирован по времени в порядке убывания. Место вставки новых данных ищется бинарным поиском. Таким образом, удаляемые данные всегда расположены в конце массива и на их удаление не нужно тратить время, а достаточно просто уменьшить счетчик nb. Такое решение сложнее, но более эффективно для большого количества данных. Вариант решения без оптимизации работы с массивом b приведен в Задаче 6412. Помимо указанных двух массивов, в программе используются следующие одномерные массивы:
total - общее количество мест по категориям;
busy - количество занятых в данный момент мест в категориях;
count - общее количество машин, припарковавшихся в каждой категории;
time - время освобождения всех парковочных мест для каждой категории.
Python
f = open('26-120.txt')
m, n = map(int, f.readline().split())
total = [int(x) for x in f.readline().split()]
busy = [0] * m
count = [0] * m
time = [0] * m
a = [[int(y) for y in x.split()] for x in f]
a.sort()
b = []
for i in a:
j = len(b) - 1
while j > -1 and b[j][0] <= i[0]:
busy[b[j][1]] -= 1
del b[j]
j -= 1
if len(b) == 0:
right = 0
else:
left = -1
right = len(b)
while left != right - 1:
center = (left + right) // 2
if b[center][0] <= i[0] + i[1]:
right = center
else:
left = center
category = -1
for j in range(i[2], m):
if total[j] > busy[j]:
category = j
break
if category != - 1:
b.insert(right, [i[0] + i[1], category])
busy[category] += 1
count[category] += 1
time[category] = max(time[category], i[0] + i[1])
mx = 0
for i in range(1, m):
if count[i] > count[mx]:
mx = i
print(time[mx], count[mx])
PascalABC
var
n, m, i, j, nb, t, right, left, center, category, min, max: Integer;
a: array [1..900, 1..3] of Integer;
b: array [1..900, 1..2] of Integer;
total, busy, count, time: array [0..5] of Integer;
f: TEXT;
begin
Assign(f, '26-120.txt');
Reset(f);
Readln(f, m, n);
for i := 0 to m - 1 do
begin
Read(f, total[i]);
busy[i] := 0;
count[i] := 0;
time[i] := 0;
end;
for i := 1 to n do
Readln(f, a[i, 1], a[i, 2], a[i, 3]);
for i := 1 to n - 1 do
begin
min := i;
for j := i + 1 to n do
if a[j, 1] < a[min, 1] then
min := j;
if min <> i then
begin
t := a[i, 1];
a[i, 1] := a[min, 1];
a[min, 1] := t;
t := a[i, 2];
a[i, 2] := a[min, 2];
a[min, 2] := t;
t := a[i, 3];
a[i, 3] := a[min, 3];
a[min, 3] := t;
end;
end;
nb := 0;
for i := 1 to n do
begin
for j := nb downto 1 do
if b[j, 1] <= a[i, 1] then
begin
busy[b[j, 2]] := busy[b[j, 2]] - 1;
nb := nb - 1
end
else
break;
if nb = 0 then
right := 1
else
begin
left := 0;
right := nb + 1;
while left <> right - 1 do
begin
center := (left + right) div 2;
if b[center, 1] <= a[i, 1] + a[i, 2] then
right := center
else
left := center
end;
end;
category := -1;
for j := a[i, 3] to m - 1 do
if total[j] > busy[j] then
begin
category := j;
break;
end;
if category <> -1 then
begin
for j := nb downto right do
begin
b[j + 1, 1] := b[j, 1];
b[j + 1, 2] := b[j, 2];
end;
nb := nb + 1;
b[right, 1] := a[i, 1] + a[i, 2];
b[right, 2] := category;
busy[category] := busy[category] + 1;
count[category] := count[category] + 1;
if a[i, 1] + a[i, 2] > time[category] then
time[category] := a[i, 1] + a[i, 2];
end;
end;
max := 0;
for i := 0 to m - 1 do
if count[i] > count[max] then
max := i;
Writeln(time[max], ' ', count[max]);
end.
C++
#include <iostream>
#include <fstream>
using namespace std;
int main()
{
ifstream f;
f.open("26-120.txt");
int m, n;
f >> m >> n;
int total[6], busy[6], count[6], time[6];
int a[900][3], b[900][2];
for (int i = 0; i < m; i++)
{
f >> total[i];
busy[i] = 0;
count[i] = 0;
time[i] = 0;
}
for (int i = 0; i < n; i++)
f >> a[i][0] >> a[i][1] >> a[i][2];
for (int i = 0; i < n - 1; i++)
{
int min = i;
for (int j = i + 1; j < n; j++)
if (a[j][0] < a[min][0])
min = j;
if (min != i)
{
int t = a[i][0];
a[i][0] = a[min][0];
a[min][0] = t;
t = a[i][1];
a[i][1] = a[min][1];
a[min][1] = t;
t = a[i][2];
a[i][2] = a[min][2];
a[min][2] = t;
}
}
int nb = 0;
for (int i = 0; i < n; i++)
{
for (int j = nb - 1; j >= 0; j--)
if (b[j][0] <= a[i][0])
{
busy[b[j][1]]--;
nb--;
}
else
break;
int left, right, center;
if (nb == 0)
right = 0;
else
{
left = -1;
right = nb;
while (left != right - 1)
{
center = (left + right) / 2;
if (b[center][0] <= a[i][0] + a[i][1])
right = center;
else
left = center;
}
}
int category = -1;
for (int j = a[i][2]; j < m; j++)
if (total[j] > busy[j])
{
category = j;
break;
}
if (category != -1)
{
for (int j = nb - 1; j >= right; j--)
{
b[j + 1][0] = b[j][0];
b[j + 1][1] = b[j][1];
}
nb++;
b[right][0] = a[i][0] + a[i][1];
b[right][1] = category;
busy[category]++;
count[category]++;
if (a[i][0] + a[i][1] > time[category])
time[category] = a[i][0] + a[i][1];
}
}
int max = 0;
for (int i = 1; i < m; i++)
if (count[i] > count[max])
max = i;
cout << time[max] << " " << count[max] << endl;
}
Ответ
194534 140