Когда потеплеет
Дан ряд среднесуточных температур за n дней. Для каждого дня найдите, через сколько дней наступит первый день строго теплее него (0, если такого нет). Выведите четыре числа: сумму всех ожиданий, самое долгое ожидание, номер дня, с которого оно начинается (самый ранний, если таких несколько), и сколько дней так и не дождались более тёплого.
Второй тест — Алматы за 1941–2025 годы (реанализ ERA5), в десятых долях градуса: после 1 августа 1946 года более тёплого дня пришлось ждать до июля 2021-го. Третий — последние десять лет.
Вход
В первой строке n (1 ≤ n ≤ 2·10⁵), во второй — n целых чисел по модулю не больше 10⁶.
Выход
Четыре числа через пробел: сумма ожиданий, самое долгое ожидание, номер его первого дня (с единицы), число дней без более тёплого.
Примеры
Пример 1
8 73 74 75 71 69 72 76 73
10 4 3 2
Ограничения
- Время · Python
- 4000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 8 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Идите по дням слева направо и держите дни, которые ещё ждут ответа. Что можно сказать о температурах этих дней, если ни один из них ещё не дождался?
2Идея
Ждущие дни образуют стек, и их температуры не растут снизу вверх: если бы более поздний ждущий день был теплее раннего, ранний уже дождался бы. Новый день снимает с вершины всех, кто холоднее его, — для каждого из них он и есть первый более тёплый, — и сам ложится на стек.
3Разбор
Каждый день один раз ложится на стек и не больше одного раза снимается, поэтому проход линейный, хотя внутри цикла есть ещё один цикл. Дни, которые остались на стеке в конце, так и не дождались. Сравнение строгое: день той же температуры ожидание не заканчивает.
Сумма ожиданий доходит до 2·10¹⁰: если все дни одинаковые, а теплее только последний (восьмой тест), каждый ждёт до самого конца. В Go её держим в int64.
3+Решение
4Сложность
O(n) времени и O(n) памяти на стек.
5Типичные ошибки
- Смотреть вперёд от каждого дня. Верно, но в ряду, который всё время холодает (четвёртый тест), каждый день просматривает весь остаток: 2·10¹⁰ сравнений.
- Нестрогое сравнение. «Не холоднее» вместо «теплее» даёт другие ожидания на днях с одинаковой температурой — пятый тест из одних пятёрок.
- Самый поздний из равных рекордов. Номер дня нужен самый ранний.