Задача 6396. Источник: Поляков. Задание КИМ 26
(А. Богданов) В гостинице составляют недельный план уборки номеров после отъезда клиентов. Все номера одинаковые и пронумерованы с 1 до К. В основе плана – журнал заявок, в каждой из которых записано время заезда и время выезда для N заявок. Заявки поступают в случайном порядке. На начало недели все номера подготовлены к заселению. После отъезда клиента на уборку номера отводится 30 минут. Уборка начинается в следующую минуту после освобождения номера. Клиент может заезжать в подготовленный номер в следующую минуту после окончания уборки. Если подготовленных номеров несколько, то выбирается номер с максимальным временем простоя; из номеров с одинаковым временем простоя – последний номер. Если подготовленных номеров нет, клиент ждет первый подготовленный номер; при этом время отъезда не меняется. Если первый номер будет готов после запланированного времени отъезда, клиент не ждёт и сразу уезжает.
Определите максимальное время ожидания клиента перед заселением и последний номер, заселенный в течение этой недели.
Входные данные представлены в файле 26-117.txt следующим образом. В первой строке входных данных задается два числа: K – количество номеров (1 ≤ K ≤ 1000) и N – количество заявок (1 ≤ N ≤ 100000). В каждой из последующих N строк указано время заезда и время выезда в минутах, начиная с 0:00 воскресенья.
Запишите в ответе два числа: максимальное время ожидания клиента перед заселением и последний номер, заселенный в течение этой недели.
Пример входного файла:
2 5
10 30
15 40
40 65
55 80
56 100
При таких исходных данных первый клиент в минуту 10 сразу заезжает в номер 2, в 15-ю минуту второй клиент заезжает в номер 1 (без ожидания). На 30-й минуте первый клиент выезжает из номера 2 и в этом номере сразу начинается уборка, которая заканчивается на 60-й минуте. Поэтому третий клиент, который хотел заселиться на 40-й минуте, будет ждать 21 минуту и заселится в номер 2 на 61-й минуте. Аналогично четвёртый клиент, который хотел заселиться на 55-й минуте, должен ждать 16 минут, потому что готовый номер 1 будет готов только на 40 + 30 + 1 = 71 минуте. Последний клиент, желающий заселиться на 56-й минуте, фактически сможет сделать это только на 65 + 30 + 1 = 96 минуте, так что он будет ждать 40 минут и заселится в номер 2. Ответ: 40 2.
Решение
Обратите внимание, что для правильного решения данной задачи важно учитывать факторы, выделенные жирным шрифтом. При поиске свободного номера сравнение должно быть нестрогим, а так же не следует учитывать заселения, которые произошли на следующей неделе, т.е. спустя 10080 минут
Считываем исходные данные и сортируем их по времени заезда. Создадим массив/список rooms по числу номеров, где будет хранится последний момент времени, когда номер убирается. Изначально все заполняем нулями. Для каждой заявки ищем номер с минимальным временем освобождения, а при совпадении времени, с максимальным номером. Если такой номер есть до выезда клиента и время заезда в пределах текущей недели, сохраняем этот последний номер, анализируем время ожидания на максимальность и меняем время освобождения выбранного номера.
Python
f = open('26-117.txt')
k, n = map(int, f.readline().split())
a = [[int(y) for y in x.split()] for x in f]
a.sort()
rooms = [0] * k
mx = 0
last = 0
for i in a:
r = 0;
for j in range(1, k):
if rooms[j] <= rooms[r]:
r = j
if rooms[r] < i[1] and rooms[r] <= 10080 and i[0] <= 10080:
last = r + 1
mx = max(mx, rooms[r] - i[0] + 1)
rooms[r] = i[1] + 30
print(mx, last)
PascalABC
var
n, k, max, last, min, i, j, r, tmp: Integer;
a: array [1..149, 1..2] of Integer;
rooms: array [1..30] of Integer;
f: TEXT;
begin
Assign(f, '26-117.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
tmp := a[i, 1];
a[i, 1] := a[min, 1];
a[min, 1] := tmp;
tmp := a[i, 2];
a[i, 2] := a[min, 2];
a[min, 2] := tmp;
end;
end;
for i := 1 to k do
rooms[i] := 0;
max := 0;
last := 0;
for i := 1 to n do
begin
r := 1;
for j := 2 to k do
if rooms[j] <= rooms[r] then
r := j;
if (rooms[r] < a[i, 2]) and (rooms[r] <= 10080) and (a[i, 1] <= 10080) then
begin
last := r;
if rooms[r] - a[i, 1] + 1 > max then
max := rooms[r] - a[i, 1] + 1;
rooms[r] := a[i, 2] + 30;
end;
end;
Writeln(max, ' ', last);
end.
C++
#include <iostream>
#include <fstream>
using namespace std;
int main()
{
ifstream f;
f.open("26-117.txt");
int k, n;
f >> k >> n;
int a[149][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 rooms[30];
for (int i = 0; i < k; i++)
rooms[i] = 0;
int max = 0, last = 0;
for (int i = 0; i < n; i++)
{
int r = 0;
for (int j = 1; j < k; j++)
if (rooms[j] <= rooms[r])
r = j;
if (rooms[r] < a[i][1] && rooms[r] <= 10080 && a[i][0] <= 10080)
{
last = r + 1;
if (rooms[r] - a[i][0] + 1 > max)
max = rooms[r] - a[i][0] + 1;
rooms[r] = a[i][1] + 30;
}
}
cout << max << " " << last << endl;
}
Ответ
79 11