Гистограмма Гистограмма является многоугольником, сформированным из последовательности прямоугольников, выровненных на общей базовой линии. Прямоугольники имеют равную ширину, но могут иметь различные высоты. Например, фигура слева показывает гистограмму, которая состоит из прямоугольников с высотами 2,1,4,5,1,3,3 2 , 1 , 4 , 5 , 1 , 3 , 3 . Все прямоугольники на этом рисунке имеют ширину, равную 1 1 . Обычно гистограммы используются для представления дискретных распределений, например, частоты символов в текстах. Отметьте, что порядок прямоугольников очень важен. Вычислите область самого большого прямоугольника в гистограмме, который также находится на общей базовой линии. На рисунке справа заштрихованная фигура является самым большим выровненным прямоугольником на изображенной гистограмме. Входные данные В первой строке входных данных записано число n (0<≤106) ( 0 < n ≤ 10 6 ) — количество прямоугольников гистограммы. Далее на той же строке следуют n целых чисел ℎ1 h 1 , ..., ℎ h n , где 0≤ℎ≤109 0 ≤ h i ≤ 10 9 . Эти числа обозначают высоты прямоугольников гистограммы слева направо. Ширина каждого прямоугольника равна 1 1 . Выходные данные Выведите площадь самого большого прямоугольника в гистограмме. Помните, что этот прямоугольник должен быть на общей базовой линии. Примеры Ввод Вывод 7 2 1 4 5 1 3 3 8
#include <iostream>
typedef long long ll;
using namespace std;
bool ll_is_valid(ll t, ll N, ll x, ll y)
{
return t / x + (t - x) / y >= N;
}
ll f(ll N, ll x, ll y)
{
ll R = 1;
while (!ll_is_valid(R,N,x,y)) R *= 2;
ll L = R / 2;
while(R - L > 1)
{
ll M = (L + R) / 2;
if (!ll_is_valid(M,N,x,y)) {L = M;}
else {R = M;}
}
return R;
}
int main()
{
ll N,x,y;
cin >> N >> x >> y;
if(x > y) swap( x, y );
cout << f(N, x, y) << std::endl;
}
ответ: Повторять пункты 4, 5 ,6 до тех пор пока не будут выполнены все задания ко всем урокам.
Объяснение: Суть циклических алгоритмов в том, чтобы повторять действие, пока какое-то условие не будет выполнено, при этом повторяющиеся действия должны быть направлены на выполнение условия.
Нужно ли нам повторять действие "Сесть за стол."? - нет, потому что это нужно выполнить всего лишь единожды.
Нужно ли нам бесконечно доставать учебные принадлежности? - нет.
Что нам нужно будет делать каждый раз это читать задание к очередному уроку и подготавливать по нему устную часть и письменную часть, поскольку эти задания необходимо выполнять по-кругу, пока "не будут выполнены все задания ко всем урокам".
Единственное что - поскольку цикл абстрактный, то можно спорно говорить про разные его пункты. К примеру, под пунктом 2 могут иметься именно учебные принадлежности определённого предмета, в этом случае нам надо будет повторять это действие, потому что нам нужен всегда учебник самого предмета. Похожая ситуация с пунктом, если, к примеру, нам необходимо каждый раз смотреть расписание и брать следующий предмет из него для выполнения (к примеру мы не можем их всех запомнить посмотрев единожды).
Надеюсь это даст общее представление о том, для чего и как работают алгоритмы и почему именно эти пункты выбраны.