Задача 6541. Источник: Поляков. Задание КИМ 26
(А. Богданов) Отель расположен на берегу моря и состоит из небольших домиков, расположенных линиями от моря по К домов в линию. Первая линия домиков расположена на берегу. Перед сезоном все домики подготовлены к заселению. Все заявки на заселение записываются в журнал по мере поступления. В каждой заявке указан час заезда и час выезда, отсчёт ведётся от начала сезона. Домик считается свободным в следующий час после выезда. Домик для заселения выбирается в момент приезда. Турист всегда заселяется в первый свободный домик ближайшей к морю линии, где есть свободные домики. Определить максимальный номер линии, в которой будет заселяться хотя бы один домик и количество заселенных домиков в следующий час после заселения последнего туриста.
Входные данные представлены в файле 26-122.txt следующим образом. Первая строка входного файла содержит два натуральных числа, записанных через пробел: К (1 ≤ K ≤ 100) – количество домиков в одной линии, и N (1 ≤ N ≤ 106) - количество заявок. Каждая из N последующих строк описывает содержит два целых числа: час заезда и час выезда, считая от начала сезона.
В ответе запишите два целых числа: максимальный номер линии, в которой будет заселяться хотя бы один домик и количество заселенных домиков в следующий час после заселения последнего туриста.
Пример входного файла:
3 5
7 65
10 40
16 33
35 55
39 46
При таких исходных данных в линии по три домика. В первый день будут заселены все три домика первой линии. На следующий день заселят освободившийся дом на 1-й линии и один дом на 2-й линии. После 39 ч в отеле будет занято 4 домика. Ответ: 2 4.
Решение
Считываем исходные данные в массив/список и сортируем в порядке возрастания. Создаем массив houses, где будет храниться количество свободных домов в каждой линии. Размер данного массива лучше взять "с запасом". В массиве/списке/векторе rent будем хранить информацию об арендованных домах. В каждой записи будет два параметра: номер линии и время освобождения дома. Последовательно обрабатываем отсортированные исходные данные. Из rent удаляем все записи домов, где дома освободились до момента заселения в обрабатываемой заявке, увеличивая количество свободных домов в соответствующей линии. После этого ищем минимальный номер линии, где есть свободный дом, уменьшаем счетчик данной линии и помещаем информацию о новом доме в rent. Номер линии анализируем на максимальное значение. Вторым числом в ответе будет размер rent после обработки всех заявок аренды.
Python
f = open('26-122.txt')
k, n = map(int, f.readline().split())
a = [[int(y) for y in x.split()] for x in f]
a.sort()
houses = [k] * 1000
rent = []
maxline = 0
for i in a:
j = 0
while j < len(rent):
if rent[j][1] < i[0]:
houses[rent[j][0]] += 1
del rent[j]
else:
j += 1
for j in range(1000):
if houses[j] > 0:
houses[j] -= 1
rent.append([j, i[1]])
maxline = max(maxline, j + 1)
break
print(maxline, len(rent))
PascalABC
type
Rec = record
line: Integer;
time: Integer;
end;
var
n, k, maxline, min, i, j, t: Integer;
a: array [1..500, 1..2] of Integer;
houses: array [1..1000] of Integer;
tmp: Rec;
rent: array of Rec = new Rec[0];
f: TEXT;
begin
Assign(f, '26-122.txt');
Reset(f);
Readln(f, k, n);
for i := 1 to n do
Readln(f, a[i, 1], a[i, 2]);
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;
end;
end;
for i := 1 to 1000 do
houses[i] := k;
maxline := 0;
for i := 1 to n do
begin
j := 0;
while j < rent.Length do
if rent[j].time < a[i][1] then
begin
houses[rent[j].line] := houses[rent[j].line] + 1;
rent := rent[:j] + rent[j + 1:];
end
else
j := j + 1;
for j := 1 to 1000 do
if houses[j] > 0 then
begin
houses[j] := houses[j] - 1;
tmp.line := j;
tmp.time := a[i][2];
rent := rent + Arr(tmp);
if j > maxline then
maxline := j;
break;
end;
end;
Writeln(maxline, ' ', rent.Length);
end.
C++
#include <iostream>
#include <vector>
#include <fstream>
using namespace std;
struct rec
{
int line;
int time;
};
int main()
{
ifstream f;
f.open("26-122.txt");
int k, n;
f >> k >> n;
int a[500][2];
for (int i = 0; i < n; i++)
f >> a[i][0] >> a[i][1];
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;
}
}
int houses[1000];
vector<rec> rent;
for (int i = 0; i < 1000; i++)
houses[i] = k;
int maxline = 0;
for (int i = 0; i < n; i++)
{
int j = 0;
while (j < rent.size())
if (rent[j].time < a[i][0])
{
houses[rent[j].line]++;
rent.erase(rent.begin() + j);
}
else
j++;
for (j = 0; j < 1000; j++)
if (houses[j] > 0)
{
houses[j]--;
rec tmp;
tmp.line = j;
tmp.time = a[i][1];
rent.push_back(tmp);
if (j + 1 > maxline)
maxline = j + 1;
break;
}
}
cout << maxline << " " << rent.size() << endl;
}
Ответ
14 120