Что спрашивают
Даны N посещений в формате «номер спортсмена, номер точки». Один спортсмен может приходить в точку несколько раз. Нужно найти максимальную длину серии спортсменов с подряд идущими номерами, побывавших на одной точке.
Выведите длину серии и наименьший номер точки среди лучших. N ≤ 100 000, оба номера ≤ 10^6. Повторные посещения не добавляют спортсменов.
Приём решения
Преобразуем строки в пары (точка, спортсмен), уберём повторные пары через set и отсортируем. Сначала идут все спортсмены одной точки по возрастанию, затем следующая точка.
Текущая серия продолжается, только если точка прежняя, а номер спортсмена равен предыдущему плюс один. Иначе длина становится единицей. При улучшении длины обновим ответ, при равенстве выберем меньшую точку.
Почему можно проверять только соседей в сортировке? Любая серия подряд идущих номеров становится сплошным фрагментом списка своей точки. Пропуск в номерах однозначно разрывает серию. Один и тот же спортсмен в разных точках остаётся в обеих: удаляются только одинаковые пары.
Число всех посетивших точку не равно длине лучшей серии: номера 1, 2, 100 дают серию только два. Время O(N log N), память O(N).
Разбор на примере
Ввод
10 9 12 21 4 50 30 7 12 24 4 9 12 20 4 51 30 8 12 22 4
Вывод
3 4
| Точка | Различные номера | Лучшая серия |
|---|---|---|
| 4 | 20, 21, 22, 24 | 20–22: длина 3 |
| 12 | 7, 8, 9 | 7–9: длина 3 |
| 30 | 50, 51 | 50–51: длина 2 |
Точку 4 посетили спортсмены 20, 21, 22 и 24: лучшая серия 20–22 имеет длину 3. На точке 12 серия 7–9 тоже длины 3; второе посещение номера 9 ничего не добавляет. На точке 30 серия длины 2. Из двух лучших точек выбираем меньшую, 4.
Код на Python и C++
Вход задаёт спортсмена первым, а сортируемая пара содержит первой точку. Эта перестановка нужна для группировки, но не меняет смысл выходных чисел.
В C++ set<pair<int, int>> сам убирает повторы и хранит пары по возрастанию, так что отдельная сортировка не нужна.
import sys
def solve(visits):
ordered = sorted(set((point, athlete) for athlete, point in visits))
previous_point = previous_athlete = -1
run = best = answer = 0
for point, athlete in ordered:
if point == previous_point and athlete == previous_athlete + 1:
run += 1
else:
run = 1
if run > best or run == best and point < answer:
best, answer = run, point
previous_point, previous_athlete = point, athlete
return best, answer
if __name__ == '__main__':
data = list(map(int, sys.stdin.buffer.read().split()))
visits = list(zip(data[1::2], data[2::2]))
print(*solve(visits))
<iostream>
<set>
<utility>
using namespace std;
int main() {
int n;
cin >> n;
// set хранит пары (точка, спортсмен) без повторов и сразу по возрастанию.
set<pair<int, int>> ordered;
for (int i = 0; i < n; i++) {
int athlete, point;
cin >> athlete >> point;
ordered.insert({point, athlete});
}
int previous_point = -1, previous_athlete = -1;
int run = 0, best = 0, answer = 0;
for (auto [point, athlete] : ordered) {
if (point == previous_point && athlete == previous_athlete + 1)
run += 1;
else
run = 1;
if (run > best || (run == best && point < answer)) {
best = run;
answer = point;
}
previous_point = point;
previous_athlete = athlete;
}
cout << best << ' ' << answer << endl;
}
Типичные ошибки
- Посчитать повторные посещения
Серия состоит из разных спортсменов. Одна пара спортсмен–точка учитывается только один раз.
- Продолжить серию в следующей точке
Последовательные номера из разных точек не образуют общую серию. Проверяйте совпадение точки.
- Выбрать точку с большим числом записей
Много отдельных номеров с пропусками могут дать короткую серию. Важна длина непрерывного фрагмента номеров.