Что спрашивают
В зале M рядов по K мест. Известны N занятых кресел. Нужны два соседних свободных места в одном ряду; все кресла перед ними с теми же номерами тоже должны быть свободны.
Выберите ряд как можно дальше от сцены, затем наименьший номер первого кресла. N ≤ 10 000, M и K ≤ 100 000, K ≥ 2. Подходящая пара существует.
Приём решения
Для каждого номера места c найдём first[c] — ближайший к сцене занятый ряд в этом столбце. Если занятых нет, положим M + 1. Все кресла этого столбца до first[c] свободны; на самом first[c] садиться уже нельзя.
Для пары c и c + 1 допустимы ряды не дальше min(first[c], first[c + 1]) - 1. Эта формула сразу учитывает и сами выбранные кресла, и все кресла перед ними. Если результат ноль, пара не подходит ни в одном ряду.
Переберите c от 1 до K - 1. Запоминайте ответ только при строго большем ряде. Тогда при равных рядах автоматически сохранится меньший номер места, встреченный раньше.
Мы читаем N занятых кресел и перебираем K - 1 пар, не создавая матрицу M × K. Время O(N + K), память O(K).
Разбор на примере
Ввод
4 8 6 5 2 7 3 4 5 8 6
Вывод
6 3
| Пара мест | Первый занятый ряд из двух | Последний допустимый ряд |
|---|---|---|
| 1–2 | 5 | 4 |
| 2–3 | 5 | 4 |
| 3–4 | 7 | 6 |
| 4–5 | 4 | 3 |
| 5–6 | 4 | 3 |
Первые занятые ряды по столбцам: 9, 5, 7, 9, 4, 8, где 9 означает отсутствие занятого кресла. Для мест 3 и 4 последним допустимым будет ряд 6: кресло 3 занято уже в ряду 7. Другие пары дают ряды не дальше четвёртого.
Код на Python и C++
Индекс 0 в массиве first не используется: номера мест начинаются с единицы. Значение M + 1 позволяет выбрать последний ряд в полностью свободных столбцах.
import sys
def solve(m, k, occupied):
first = [m + 1] * (k + 1)
for row, seat in occupied:
first[seat] = min(first[seat], row)
best_row = best_seat = 0
for seat in range(1, k):
row = min(first[seat], first[seat + 1]) - 1
if row > best_row:
best_row, best_seat = row, seat
return best_row, best_seat
if __name__ == '__main__':
data = list(map(int, sys.stdin.buffer.read().split()))
n, m, k = data[:3]
occupied = list(zip(data[3::2], data[4::2]))
print(*solve(m, k, occupied))
<algorithm>
<iostream>
<vector>
using namespace std;
int main() {
int n, m, k;
cin >> n >> m >> k;
vector<int> first(k + 1, m + 1);
for (int i = 0; i < n; i++) {
int row, seat;
cin >> row >> seat;
first[seat] = min(first[seat], row);
}
int best_row = 0, best_seat = 0;
for (int seat = 1; seat < k; seat++) {
int row = min(first[seat], first[seat + 1]) - 1;
if (row > best_row) {
best_row = row;
best_seat = seat;
}
}
cout << best_row << ' ' << best_seat << endl;
}
Типичные ошибки
- Проверять только выбранный ряд
Даже свободная пара не подходит, если перед одним из кресел есть занятое место.
- Запомнить последнее занятое кресло
Пару мест ограничивает ближайшее к сцене занятое кресло с теми же номерами, а не самое дальнее. Используйте минимум номера ряда, а не максимум.
- Обновлять при равном ряде
При обходе слева направо это заменит меньший номер пары на больший. Равный ряд не улучшает ответ.