супер задача! (Придумал сам) 
Difference between ru1 and ru2, changed 2 character(s)
Условие: ↵
У Вовы есть гистограмма A. У A[i] = (h[i], w[i]); у прямоугольника A[i] есть высота h[i], и ширина w[i].↵
Он хочет достроить её до прямоугольника с минимальной площадью. Какова площадь достроенной части?↵
1 <= n <= 10 ^ 5↵
1 <= h[i], w[i] <= 10 ^ 18↵
Решение должно быть по асимптотике O(n).↵

Решение (моё): ↵
Представим каждый прямоугольник в виде клеток. Тогда будет удобно считать их площадь. ↵
Тогда получается простая формула смотри в прикреплённом файле.↵
Решение (код) Python.↵

res = 0↵
m = max(h)↵
for i in range(n):↵
    res += w[i] * (m &mdash; h[i])↵

Решение (код) С++.↵

int res;↵
int m = max(h);↵
for (int i = 0; i < n; ++i){↵
    res = res + w[i] * (m &mdash; h[i]);↵
}
Пишите свои решения в комментах! Жду!

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru3 Russian Tih_Monkes 2024-05-01 19:07:36 76
ru2 Russian Tih_Monkes 2024-05-01 18:59:15 2 Мелкая правка: '; h[i]);\n\nПишите с' -> '; h[i]);\n}\nПишите с'
ru1 Russian Tih_Monkes 2024-05-01 18:58:35 768 Первая редакция (опубликовано)