Что спрашивают

В зале 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–254
2–354
3–476
4–543
5–643

Первые занятые ряды по столбцам: 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))
#include <algorithm>
#include <iostream>
#include <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;
}

Типичные ошибки

  • Проверять только выбранный ряд

    Даже свободная пара не подходит, если перед одним из кресел есть занятое место.

  • Запомнить последнее занятое кресло

    Пару мест ограничивает ближайшее к сцене занятое кресло с теми же номерами, а не самое дальнее. Используйте минимум номера ряда, а не максимум.

  • Обновлять при равном ряде

    При обходе слева направо это заменит меньший номер пары на больший. Равный ряд не улучшает ответ.