Что спрашивают
Есть K приёмщиков: нечётные принимают сорт A, чётные — B. Партии рассматриваются по началу, затем окончанию, затем A перед B. Партию берёт свободный приёмщик нужного сорта с минимальным номером; иначе её отправляют на рынок.
После окончания приёмщик отдыхает 5 минут. Выведите число принятых партий и номер приёмщика последней принятой в порядке рассмотрения. K и N ≤ 10 000, время от 0 до 1440, нулевая длительность допустима.
Приём решения
Сортируем записи как тройки (start, end, kind). Для каждого сорта заведём две минимальные кучи: номера свободных приёмщиков и пары (время освобождения, номер) занятых.
Перед партией времени start возвращаем в свободную кучу всех приёмщиков её сорта с временем освобождения <= start. Из свободных берём минимальный номер; в занятые кладём (end + 5, номер). Если свободных нет, партия отклонена. Она не ждёт освобождения и не передаётся другому сорту.
Номер last обновляется при каждом успешном назначении. Это последний по порядку рассмотрения, а не приёмщик, завершивший работу позже всех. Освобождение другого сорта можно отложить до его следующей партии: на выбор текущей оно не влияет.
Каждая принятая партия добавляется в кучу и удаляется не более одного раза. Время O(N log N + N log(K + 1) + K), память O(N + K), включая отсортированный вход.
Разбор на примере
Ввод
3 7 25 26 A 10 20 A 19 19 A 10 12 B 20 90 A 17 22 B 10 15 A
Вывод
6 3
| Партия после сортировки | Решение | Освобождение приёмщика |
|---|---|---|
| 10–12, B | Номер 2 | 17 |
| 10–15, A | Номер 1 | 20 |
| 10–20, A | Номер 3 | 25 |
| 17–22, B | Номер 2 | 27 |
| 19–19, A | На рынок | Свободных A нет |
| 20–90, A | Номер 1 | 95 |
| 25–26, A | Номер 3; последняя | 31 |
В момент 10 сначала рассматривается B до 12, затем A до 15 и A до 20. Их принимают номера 2, 1 и 3. В 19 оба нечётных ещё заняты с учётом паузы. В 20 номер 1 уже доступен; в 25 доступен номер 3. Последняя принятая партия достаётся номеру 3, хотя номер 1 закончит позже.
Код на Python и C++
Начальные списки номеров уже возрастают, поэтому удовлетворяют свойству минимальной кучи. Английские A и B сортируются в нужном порядке.
В C++ кучи — priority_queue. По умолчанию она отдаёт наибольший элемент, поэтому третьим параметром указан greater: так сверху оказывается наименьший, как в heapq.
import heapq
import sys
def solve(k, records):
free = [list(range(1, k + 1, 2)), list(range(2, k + 1, 2))]
busy = [[], []]
accepted = last = 0
for start, end, kind in sorted(records):
group = 0 if kind == 'A' else 1
while busy[group] and busy[group][0][0] <= start:
_, receiver = heapq.heappop(busy[group])
heapq.heappush(free[group], receiver)
if not free[group]:
continue
receiver = heapq.heappop(free[group])
heapq.heappush(busy[group], (end + 5, receiver))
accepted += 1
last = receiver
return accepted, last
if __name__ == '__main__':
stream = sys.stdin
k, n = map(int, stream.readline().split())
records = []
for _ in range(n):
start, end, kind = stream.readline().split()
records.append((int(start), int(end), kind))
print(*solve(k, records))
<algorithm>
<functional>
<iostream>
<queue>
<tuple>
<utility>
<vector>
using namespace std;
int main() {
int k, n;
cin >> k >> n;
vector<tuple<long long, long long, char>> records(n);
for (auto& [start, end, kind] : records)
cin >> start >> end >> kind;
sort(records.begin(), records.end());
// Минимальные кучи: номера свободных и пары (время освобождения, номер) занятых.
priority_queue<int, vector<int>, greater<int>> free[2];
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> busy[2];
for (int receiver = 1; receiver <= k; receiver++)
free[receiver % 2 == 1 ? 0 : 1].push(receiver);
int accepted = 0, last = 0;
for (auto [start, end, kind] : records) {
int group = kind == 'A' ? 0 : 1;
while (!busy[group].empty() && busy[group].top().first <= start) {
free[group].push(busy[group].top().second);
busy[group].pop();
}
if (free[group].empty())
continue;
int receiver = free[group].top();
free[group].pop();
busy[group].push({end + 5, receiver});
accepted += 1;
last = receiver;
}
cout << accepted << ' ' << last << endl;
}
Типичные ошибки
- Дать приёмщику ждать партию или партии ждать
Назначенное начало фиксировано. При нехватке свободных партию сразу отправляют на рынок.
- Не прибавить пять минут
Приёмщик доступен только начиная с end + 5. В точности в этот момент новую партию принять уже можно.
- Выбрать последнего по окончанию
Последняя принятая партия определяется порядком сортировки и успешного назначения, а не временем завершения.