Задача 6838. Источник: Поляков. Задание КИМ 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 1.
Решение
Исходные данные считываем в массив/список и сортируем по времени заказа. Помимо этого в переменной available будем хранить количество имеющихся самокатов на каждой парковке, в переменной need - сколько самокатов на каждой парковке потребуется, а в переменной way - информацию о самокатах, которые находятся в пути.
Прежде чем обработать очередную заявку, удаляем в массиве/списке way все записи о самокатах, которые прибыли к моменту начала аренды в обрабатываемом заказе, увеличивая счетчики available на стоянках прибытия. Если на стоянке отправления рассматриваемой заявки имеются самокаты, то уменьшаем счетчик на единицу. Если свободных самокатов нет, увеличиваем счетчик необходимых самокатов в need. После этого заявку помещаем в way. Размер списка way является количеством одновременно арендуемых самокатов. Обработав заявку, анализируем этот параметр на максимальность. После обработки всех заказов, находим в need стоянку с наибольшим количество требуемых самокатов и выводим ответ.
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)
need = [0] * (m + 1)
way = []
mx = 0
mxtime = 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:
need[i[2]] += 1
way.append(i)
if len(way) > mx:
mx = len(way)
mxtime = i[0]
print(mxtime, need.index(max(need)))
PascalABC
type
Rec = record
start: Integer;
time: Integer;
pfrom: Integer;
pto: Integer;
end;
var
n, m, max, min, maxtime, i, j: Integer;
a: array [1..1000] of Rec;
available, need: 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
begin
available[i] := 0;
need[i] := 0;
end;
max := 0;
maxtime := 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
need[t.pfrom] := need[t.pfrom] + 1;
way := way + Arr(t);
if way.Length > max then
begin
max := way.Length;
maxtime := t.start;
end;
end;
max := 1;
for i := 2 to m do
if need[i] > need[max] then
max := i;
Writeln(maxtime, ' ', 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], need[21];
vector<rec> way;
for (int i = 0; i <= m; i++)
{
available[i] = 0;
need[i] = 0;
}
int max = 0, maxtime = 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
need[t.pfrom]++;
way.push_back(t);
if (way.size() > max)
{
max = way.size();
maxtime = t.start;
}
}
max = 1;
for (int i = 2; i <= m; i++)
if (need[i] > need[max])
max = i;
cout << maxtime << " " << max << endl;
}
Ответ
400 13