Задача 7187. Источник: Поляков. Задание КИМ 26
На автозаправке работают K заправочных колонок. Некоторые машины могут заправляться только на определённых колонках, потому что на других отсутствует нужное им топливо. Клиент заезжает на заправку и встаёт в очередь к той колонке, в которой есть необходимое ему топливо. Если нужное топливо есть во всех колонках, клиент выбирает ту, очередь к которой в данный момент меньше. Если таких колонок несколько, клиент выбирает колонку с меньшим номером. Если при этом в очереди к выбранной колонке уже стоит 5 или более машин (считая ту машину, которая сейчас заправляется), клиент сразу уезжает.
Входные данные представлены в файле 26-144.txt следующим образом. В первой строке входного файла содержит натуральные числа N (1 ≤ N ≤ 1000) – количество клиентов, которые заезжали на заправку в течение дня, и K (1 ≤ K ≤ 10) – количество заправочных колонок. Каждая из следующих N строк описывает одного клиента и содержит 3 целых числа: время приезда клиента на заправку (количество минут с начала рабочего дня); время, необходимое для заправки, и номер колонки, в которое ему необходимо заправляться (0 означает, что клиент может заправляться на любой колонке). Гарантируется, что никакие два клиента не приезжают одновременно.
Запишите в ответе два числа: количество машин, которые будут заправлены в течение дня на колонке с номером K, и количество клиентов, которые уехали с заправки из-за очередей.
Пример входного файла:
5 2
10 5 0
11 3 1
12 4 0
13 4 1
15 5 0
Предположим, что клиент уезжает, если очередь к нужной ему колонке включает более одной машины. При таких исходных данных на второй колонке заправятся третья и пятая машины, а четвёртый клиент уедет, поскольку ему нужна первая колонка, где в очереди в момент 13 находятся две машины. Ответ: 2 1.
Решение
Считываем данные и сортируем их в порядке возрастания времени приезда автомобилей. В переменной k1 будем подсчитывать количество автомобилей, заправившихся на k-ой колонке, а в переменной k2 - количество автомобилей, которые не смогли заправиться. Помимо этого создадим для каждой колонки список/массив/вектор, где будем хранить время завершения заправки автомобилей в очереди. Удобнее хранить эти очереди в виде массива/списка queues. Последовательно обрабатываем отсортированные данные. Из всех очередей удаляем информацию об автомобилях, которые завершили заправку до визита рассматриваемого автомобиля. Если автомобиль может заправиться в любой заправке, выбираем заправку с наименьшей очередью. Если в очереди менее пяти автомобилей, добавляем время окончания заправки автомобиля в очередь. Если это k-ая заправка, увеличиваем k1. Если автомобиль не может заправиться, увеличиваем k2. После обработки всех данных, выводим результат.
Python
f = open('26-144.txt')
n, k = map(int, f.readline().split())
a = [[int(y) for y in x.split()] for x in f]
a.sort()
queues = [[] for i in range(k)]
k1 = 0
k2 = 0
for i in a:
for j in range(k):
z = 0
while z < len(queues[j]):
if queues[j][z] <= i[0]:
del queues[j][z]
else:
z += 1
if i[2] == 0:
i[2] = 1
for j in range(2, k + 1):
if len(queues[j - 1]) < len(queues[i[2] - 1]):
i[2] = j
if len(queues[i[2] - 1]) < 5:
if i[2] == k:
k1 += 1
if len(queues[i[2] - 1]) == 0:
queues[i[2] - 1].append(i[0] + i[1])
else:
queues[i[2] - 1].append(queues[i[2] - 1][-1] + i[1])
else:
k2 += 1
print(k1, k2)
PascalABC
type
qarray = array of Integer;
var
n, k, k1, k2, min, z, i, j, t: Integer;
a: array [1..1000, 1..3] of Integer;
queues: array [1..5] of qarray;
f: TEXT;
begin
Assign(f, '26-144.txt');
Reset(f);
Readln(f, n, k);
for i := 1 to n do
Readln(f, a[i, 1], a[i, 2], a[i, 3]);
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;
t := a[i, 3];
a[i, 3] := a[min, 3];
a[min, 3] := t;
end;
end;
k1 := 0;
k2 := 0;
for i := 1 to 5 do
queues[i] := new Integer[0];
for i := 1 to n do
begin
for j := 1 to k do
begin
z := 0;
while z < queues[j].Length do
if queues[j][z] <= a[i][1] then
if z < queues[j].Length - 1 then
queues[j] := queues[j][:z] + queues[j][z + 1:]
else
queues[j] := queues[j][:z]
else
z := z + 1;
end;
if a[i][3] = 0 then
begin
a[i][3] := 1;
for j := 2 to k do
if queues[j].Length < queues[a[i][3]].Length then
a[i][3] := j;
end;
if queues[a[i][3]].Length < 5 then
begin
if a[i][3] = k then
k1 := k1 + 1;
if queues[a[i][3]].Length = 0 then
queues[a[i][3]] := Arr(a[i][1] + a[i][2])
else
queues[a[i][3]] := queues[a[i][3]] +
Arr(queues[a[i][3]][queues[a[i][3]].Length - 1] + a[i][2]);
end
else
k2 := k2 + 1;
end;
Writeln(k1, ' ', k2);
end.
C++
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
int main()
{
ifstream f;
f.open("26-144.txt");
int n, k;
f >> n >> k;
int a[1000][3];
for (int i = 0; i < n; i++)
f >> a[i][0] >> a[i][1] >> a[i][2];
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;
t = a[i][2];
a[i][2] = a[min][2];
a[min][2] = t;
}
}
int k1 = 0, k2 = 0;
vector<int> queues[5];
for (int i = 0; i < n; i++)
{
for (int j = 0; j < k; j++)
{
int z = 0;
while (z < queues[j].size())
if (queues[j][z] <= a[i][0])
queues[j].erase(queues[j].begin() + z);
else
z++;
}
if (a[i][2] == 0)
{
a[i][2] = 1;
for (int j = 2; j <= k; j++)
if (queues[j - 1].size() < queues[a[i][2] - 1].size())
a[i][2] = j;
}
if (queues[a[i][2] - 1].size() < 5)
{
if (a[i][2] == k)
k1++;
if (queues[a[i][2] - 1].size() == 0)
queues[a[i][2] - 1].push_back(a[i][0] + a[i][1]);
else
queues[a[i][2] - 1].push_back(*(queues[a[i][2] - 1].end() - 1) + a[i][1]);
}
else
k2++;
}
cout << k1 << " " << k2 << endl;
}
Ответ
179 6