Градусо-часы по датчику с пропусками
Уличный датчик умного термостата присылает температуру когда получится: обычно раз в час, но связь пропадает, и между показаниями бывает и пять минут, и полдня. Чтобы оценить, сколько тепла ушло на отопление, нужны градусо-часы: интеграл по времени от того, на сколько градусов на улице холоднее заданной температуры B. Когда теплее, чем B, в интеграл идёт ноль, а не отрицательное число.
Между двумя показаниями считайте, что температура менялась равномерно, по прямой. Посчитайте градусо-часы от первого показания до последнего.
Второй пример — настоящий день в Алматы, 4 апреля 2025 года, а среди закрытых тестов — весь отопительный сезон по часам (реанализ ERA5-Land через Open-Meteo, CC BY 4.0).
Вход
В первой строке n и B (1 ≤ n ≤ 200 000, −600 ≤ B ≤ 600). Дальше n строк t T: время показания в минутах от начала наблюдений и температура в десятых долях градуса (0 ≤ t ≤ 2·10⁹, моменты строго возрастают; −600 ≤ T ≤ 600). B тоже в десятых долях градуса.
Выход
Одно число — градусо-часы (градусы, а не десятые, умноженные на часы). Ответ принимается с относительной ошибкой до 10⁻⁶.
Примеры
Пример 1
3 180 0 200 60 160 120 160
2.500000
Пример 2
8 180 480 99 600 136 660 169 780 203 840 205 1020 187 1080 170 1200 132
21.700000
Ограничения
- Время · Python
- 4000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 10 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Первый пример: в полночь +20 °C, через час +16 °C, ещё через час +16 °C, а B = 18 °C. Нарисуйте график и закрасьте то, что нужно сложить. Это две трапеции?
2Подсказка 2
На отрезке между двумя показаниями недостающая до B разница — линейная функция времени. Положительная часть линейной функции бывает трёх видов: вся, никакая или треугольник до точки, где прямая пересекает ноль.
3Идея
Это интеграл функции, заданной таблицей, и между точками мы обязались считать её линейной — значит, формула трапеций для самой температуры точна. Но интегрируем мы не температуру, а max(0, B − T), и у этой функции излом там, где T пересекает B. Внутри отрезка, где пересечения нет, — обычная трапеция. Где есть, интеграл — площадь треугольника: прямая от g₀ > 0 до g₁ < 0 пересекает ноль на доле g₀/(g₀ − g₁) отрезка, и площадь равна g₀² / (g₀ − g₁) · Δt / 2.
4Разбор
Для каждой пары соседних показаний считаем g₀ = B − Ti и g₁ = B − Ti+1. Оба не меньше нуля — прибавляем (g₀ + g₁)/2 · Δt. Оба не больше нуля — ничего. Разных знаков — треугольник с вершиной у того конца, где разница положительна. Шаги разные, и каждая трапеция берёт свою ширину: формула трапеций не требует равных промежутков, в отличие от Симпсона. В конце делим на 10 (десятые доли градуса) и на 60 (минуты в часы).
Почему нельзя сначала обрезать показания нулём, а потом сложить трапеции. В первом примере обрезанные разницы — 0, 2 и 2 градуса, и трапеции дают 1 + 2 = 3 градусо-часа. Но в первый час температура опускалась ниже 18 °C только во второй его половине: настоящая площадь — треугольник 0,5 градусо-часа, и ответ 2,5. Обрезка «размазывает» излом по всему отрезку. На зимних данных, где температура почти всегда ниже 18 °C, ошибка маленькая, но весной пересечения каждый день, и она растёт.
4+Решение
5Сложность
O(n) времени, памяти — O(n) на чтение, хотя хватило бы и O(1): нужны только два соседних показания.
6Типичные ошибки
- Обрезать до сложения. max(0, B − T) в точках, потом трапеции — переоценка на каждом пересечении B; первый тест.
- Считать шаг равным часу. Показания приходят неравномерно; ширина трапеции — разница моментов, а не номер показания.
- Отрицательные вклады. Если сложить трапеции для B − T без обрезки, тёплые часы вычтутся из холодных, хотя тепла назад в дом они не возвращают.
- Один показ — ноль. При n = 1 время не прошло, ответ 0.