Задача 6321. Источник: Поляков. Задание КИМ 26
(Л. Евич) В операционном зале есть N банкоматов, работающих круглосуточно. Все банкоматы пронумерованы. В течение дня M клиентов хотят воспользоваться банкоматом. Клиенты обслуживаются в порядке общей очереди. Если в один момент подошли несколько клиентов, то они становятся в очередь в порядке расположения данных в файле. Клиент, стоящий первым в очереди, подходит к первому освободившемуся банкомату (если таких несколько – к банкомату с наименьшим номером). Обслуживание очередного клиента может начаться в ту же минуту, когда банкомат станет свободным. Известно время в минутах от начала суток, когда клиент подошёл к банкомату, и время его обслуживания.
Определите наибольшее время (в минутах), которое клиент стоял в очереди, и время начала обслуживания последнего клиента в том банкомате, в котором было обслужено наибольшее количество клиентов. Если таких банкоматов несколько, укажите наименьший подходящий номер банкомата.
Входные данные представлены в файле 26-112.txt следующим образом. В первой строке входных данных задается два числа: N - количество банкоматов и M – количество клиентов. В каждой из последующих M строк содержится информация по одному клиенту: время начала обслуживания клиента (в минутах с начала суток) и время обслуживания (в минутах).
Запишите в ответе два числа: наибольшее время (в минутах), которое клиент стоял в очереди, и время начала обслуживания последнего клиента в том банкомате, в котором было обслужено наибольшее количество клиентов.
Пример входного файла:
2 5
1 8
6 12
8 4
8 14
8 9
При таких исходных данных наибольшее время ожидания (10) будет у клиента со временем обслуживания 9. Наибольшее число клиентов (3) обслужит 1-й банкомат: это клиенты со временем обслуживания 8, 4 и 14. Последний клиент начинает работу со 1-м банкоматом на 13-й минуте. Ответ: 10 13.
Решение
Вопрос в задаче сформулирован неполностью. Приведенному ответу соответствует решение, когда ищется максимальное время ожидания за первые сутки и время начала обслуживания последнего клиента в банкомате за первые сутки, который обслужил наибольшее количество клиентов за сутки. Решение реализовано под данную формулировку.
Считываем данные и сортируем их по времени подхода к банкомату. Обратите внимание, что в данной задаче следует использовать алгоритм стабильной сортировки (пузырьковая или сортировка вставкой), чтобы сохранить порядок клиентов с одинаковым временем начала обслуживания. Создадим массив/список atms по количеству банкоматов. Для каждого банкомата будем хранить количество обслуженных клиентов, время начала обслуживания последнего клиента за первые сутки и время освобождения банкомата текущим клиентом. Последовательно обрабатываем список клиентов. Если имеются свободные банкоматы, находим банкомат с наименьшим номером из свободных, а, если нет, с наименьшим временем освобождения. Если время освобождения находится в пределах первых суток, меняем у банкомата время начала обслуживания последнего клиента, анализируем время ожидания на максимальное значение и увеличиваем счетчик обслуженных клиентов. Меняем время освобождения банкомата. При изменении времени освобождения учитываем, что банкомат мог простаивать или сразу начать обслуживание клиента из очереди. После обработки всех клиентов, находим банкомат с наибольшим числом обслуженных клиентов и выводим результат.
Python
f = open('26-112.txt')
n, m = map(int, f.readline().split())
a = [[int(y) for y in x.split()] for x in f]
a.sort(key=lambda x: x[0])
atms = [[0] * 3 for i in range(n)]
mx = 0
for i in a:
atm = 0
for j in range(1, n):
if atms[j][2] < atms[atm][2] and atms[atm][2] > i[0]:
atm = j
if atms[atm][2] <= 1440:
atms[atm][1] = atms[atm][2]
mx = max(mx, atms[atm][2] - i[0])
atms[atm][0] += 1
atms[atm][2] = max(atms[atm][2], i[0]) + i[1]
mxi = 0
for i in range(1, n):
if atms[i][0] > atms[mxi][0]:
mxi = i
print(mx, atms[mxi][1])
PascalABC
var
n, m, max, maxi, atm, i, j, t: Integer;
a: array [1..3500, 1..2] of Integer;
atms: array [1..20, 1..3] of Integer;
f: TEXT;
begin
Assign(f, '26-112.txt');
Reset(f);
Readln(f, n, m);
for i := 1 to m do
Readln(f, a[i, 1], a[i, 2]);
for i := 1 to m - 1 do
for j := m downto i + 1 do
if a[j, 1] < a[j - 1, 1] then
begin
t := a[j, 1];
a[j, 1] := a[j - 1, 1];
a[j - 1, 1] := t;
t := a[j, 2];
a[j, 2] := a[j - 1, 2];
a[j - 1, 2] := t;
end;
for i := 1 to n do
begin
atms[i, 1] := 0;
atms[i, 2] := 0;
atms[i, 3] := 0;
end;
max := 0;
for i := 1 to m do
begin
atm := 1;
for j := 2 to n do
if (atms[j, 3] < atms[atm, 3]) and (atms[atm][3] > a[i, 1]) then
atm := j;
if atms[atm, 3] <= 1440 then
begin
atms[atm, 2] := atms[atm, 3];
if atms[atm, 3] - a[i,1] > max then
max:= atms[atm, 3] - a[i,1];
atms[atm, 1] := atms[atm, 1] + 1;
end;
if atms[atm, 3] > a[i, 1] then
atms[atm, 3] := atms[atm, 3] + a[i, 2]
else
atms[atm, 3] := a[i, 1] + a[i, 2];
end;
maxi := 1;
for i := 2 to n do
if atms[i, 1] > atms[maxi, 1] then
maxi := i;
Writeln(max, ' ', atms[maxi, 2]);
end.
C++
#include <iostream>
#include <fstream>
using namespace std;
int main()
{
ifstream f;
f.open("26-112.txt");
int n, m;
f >> n >> m;
int a[3500][2];
for (int i = 0; i < m; i++)
f >> a[i][0] >> a[i][1];
for (int i = 0; i < m - 1; i++)
for (int j = m - 1; j > i; j--)
if (a[j][0] < a[j - 1][0])
{
int t = a[j][0];
a[j][0] = a[j - 1][0];
a[j - 1][0] = t;
t = a[j][1];
a[j][1] = a[j - 1][1];
a[j - 1][1] = t;
}
int atms[20][3];
for (int i = 0; i < n; i++)
{
atms[i][0] = 0;
atms[i][1] = 0;
atms[i][2] = 0;
}
int max = 0;
for (int i = 0; i < m; i++)
{
int atm = 0;
for (int j = 1; j < n; j++)
if (atms[j][2] < atms[atm][2] && atms[atm][2] > a[i][0])
atm = j;
if (atms[atm][2] <= 1440)
{
atms[atm][1] = atms[atm][2];
if (atms[atm][2] - a[i][0] > max)
max = atms[atm][2] - a[i][0];
atms[atm][0]++;
}
if (atms[atm][2] > a[i][0])
atms[atm][2] += a[i][1];
else
atms[atm][2] = a[i][0] + a[i][1];
}
int maxi = 0;
for (int i = 1; i < n; i++)
if (atms[i][0] > atms[maxi][0])
maxi = i;
cout << max << " " << atms[maxi][1] << endl;
}
Ответ
663 1432