Задача 6560. Источник: Поляков. Задание КИМ 26
(А. Богданов) Проводится вычислительный эксперимент для определения необходимого количества самокатов на разных парковках города в начальный момент времени. Всего есть M парковок с номерами от 1 до М. Поступило всего N заявок на аренду самокатов. В каждой заявке указано время начала аренды в минутах от начала суток, продолжительность аренды, а также номера парковок старта и финиша. Определите сколько всего нужно самокатов, чтобы все заявки были выполнены, и какое наибольшее число самокатов в какой-то момент будут в аренде одновременно. Будем считать, что заряда самоката хватает на весь день и самокат может быть арендован со следующей минуты после окончания предыдущей аренды.
Входные данные представлены в файле 26-123.txt следующим образом. Первая строка входного файла содержит два натуральных числа, записанных через пробел: M (1 ≤ M ≤ 100) – количество парковок, и N (1 ≤ N ≤ 106) – количество заявок. Каждая из N последующих строк описывает содержит четыре целых числа: время начала аренды в минутах от начала суток, длительность аренды в минутах, номер парковки старта и номер парковки финиша.
В ответе запишите два числа: сначала необходимое количество самокатов, затем наибольшее количество самокатов, которые в какой-то момент будут в аренде одновременно.
Пример входного файла:
2 3
1 4 2 2
3 6 1 1
5 9 1 2
При таких исходных данных нужно три самоката: два в начале размещаются на парковке 1 и один – на парковке 2. Одновременно в аренде находятся максимум два самоката (с 3-й по 8-ю минуту включительно). Ответ: 3 2.
Решение
Считываем исходные данные в массив/список и сортируем их по времени заказа. Создадим массив/список available, где будет хранится количество самокатов на каждой стоянке, в динамическом массиве/списке/векторе way будем хранить информацию о самокатах, которые находятся в пути. В переменной total будем подсчитывать необходимое количество самокатов. Последовательно обрабатываем заявки. Сначала удаляем из way все записи о самокатах, прибывших в пункты назначения до заказа обрабатываемой заявки, увеличивая счетчики стоянок прибытия. Если на стоянке отправления есть самокаты, то уменьшаем счетчик на единицу. Если доступных самокатов нет, то увеличиваем total на единицу. После этого добавляем заявку в way. Размер данного набора данных будет количеством самокатов в аренде в данный момент. Анализируем это значение на максимальность, помещая результат в переменную max (mx).
Python
f = open('26-123.txt')
m, n = map(int, f.readline().split())
a = [[int(y) for y in x.split()] for x in f]
a.sort()
available = [0] * (m + 1)
total = 0
way = []
mx = 0
for i in a:
j = 0
while j < len(way):
if way[j][0] + way[j][1] <= i[0]:
available[way[j][3]] += 1
del way[j]
else:
j += 1
if available[i[2]] > 0:
available[i[2]] -= 1
else:
total += 1
way.append(i)
mx = max(mx, len(way))
print(total, mx)
PascalABC
type
Rec = record
start: Integer;
time: Integer;
pfrom: Integer;
pto: Integer;
end;
var
n, m, max, min, total, i, j: Integer;
a: array [1..1000] of Rec;
available: array[1..20] of Integer;
way: array of Rec = new Rec[0];
t: Rec;
f: TEXT;
begin
Assign(f, '26-123.txt');
Reset(f);
Readln(f, m, n);
for i := 1 to n do
Readln(f, a[i].start, a[i].time, a[i].pfrom, a[i].pto);
for i := 1 to n - 1 do
begin
min := i;
for j := i + 1 to n do
if a[j].start < a[min].start then
min := j;
if min <> i then
begin
t := a[i];
a[i] := a[min];
a[min] := t;
end;
end;
for i := 1 to m do
available[i] := 0;
total := 0;
max := 0;
foreach t in a do
begin
i := 0;
while i < way.Length do
if way[i].start + way[i].time <= t.start then
begin
available[way[i].pto] := available[way[i].pto] + 1;
way := way[:i] + way[i + 1:];
end
else
i := i + 1;
if available[t.pfrom] > 0 then
available[t.pfrom] := available[t.pfrom] - 1
else
total := total + 1;
way := way + Arr(t);
if way.Length > max then
max := way.Length;
end;
Writeln(total, ' ', max);
end.
C++
#include <iostream>
#include <vector>
#include <fstream>
using namespace std;
struct rec
{
int start;
int time;
int pfrom;
int pto;
};
int main()
{
ifstream f;
f.open("26-123.txt");
int n, m;
f >> m >> n;
rec a[1000];
for (int i = 0; i < n; i++)
f >> a[i].start >> a[i].time >> a[i].pfrom >> a[i].pto;
for (int i = 0; i < n - 1; i++)
{
int min = i;
for (int j = i + 1; j < n; j++)
if (a[j].start < a[min].start)
min = j;
if (min != i)
{
rec t = a[i];
a[i] = a[min];
a[min] = t;
}
}
int available[21];
vector<rec> way;
for (int i = 0; i <= m; i++)
available[i] = 0;
int max = 0, total = 0;
for (rec t : a)
{
int i = 0;
while (i < way.size())
if (way[i].start + way[i].time <= t.start)
{
available[way[i].pto]++;
way.erase(way.begin() + i);
}
else
i++;
if (available[t.pfrom] > 0)
available[t.pfrom]--;
else
total++;
way.push_back(t);
if (way.size() > max)
max = way.size();
}
cout << total << " " << max << endl;
}
Ответ
192 86