Условие: ↵
У Вовы есть гистограмма 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 — h[i])↵
↵
Решение (код) С++.↵
↵
int res;↵
int m = max(h);↵
for (int i = 0; i < n; ++i){↵
res = res + w[i] * (m — h[i]);↵
}↵
Пишите свои решения в комментах! Жду!↵
Формула: /predownloaded/47/c9/47c982d55d175c55634c5778efe1ee2fc55e8973.png
У Вовы есть гистограмма 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 — h[i])↵
↵
Решение (код) С++.↵
↵
int res;↵
int m = max(h);↵
for (int i = 0; i < n; ++i){↵
res = res + w[i] * (m — h[i]);↵
}↵
Пишите свои решения в комментах! Жду!↵
Формула: /predownloaded/47/c9/47c982d55d175c55634c5778efe1ee2fc55e8973.png
