Нужно оптимизировать код

@Bluestick · Регистрация: 15.07.2019

Студворк — интернет-сервис помощи студентам

Гистограмма является многоугольником, сформированным из последовательности прямоугольников, выровненных на общей базовой линии. Прямоугольники имеют равную ширину, но могут иметь различные высоты. Например, фигура слева показывает гистограмму, которая состоит из прямоугольников с высотами 2, 1, 4, 5, 1, 3, 3.
Обычно гистограммы используются для представления дискретных распределений, например, частоты символов в текстах. Отметьте, что порядок прямоугольников очень важен. Вычислите область самого большого прямоугольника в гистограмме, который также находится на общей базовой линии.

Входные данные
В первой строке входного файла записано число N (0 < N ≤ 10^6) - количество прямоугольников гистограммы. Затем следует N целых чисел h^1 h^n, где 0 ≤ h^i ≤ 10^9. Эти числа обозначают высоты прямоугольников гистограммы слева направо. Ширина каждого прямоугольника равна 1

Выходные данные
Выведите площадь самого большого прямоугольника в гистограмме. Помните, что этот прямоугольник должен быть на общей базовой линии.

Примеры
входные данные
7 2 1 4 5 1 3 3
выходные данные
8
Есть код, но не проходит 1 тест по времени (ограничение 1 сек. у меня этот тест проходит за 1.096)

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <stdio.h>
 
#define MAX 1000010
 
 
 
long long h[MAX];
 
int i, n, left, right;
 
long long area, res;
 
 
 
int main(void)
 
{
 
  scanf("%d",&n);
 
  for(i = 1; i <= n; i++)
 
    scanf("%d",&h[i]);
 
 
 
  res = 0;
 
  for(i = 1; i <= n; i++)
 
  {
 
    left = right = i;
 
    while(left > 1 && h[left-1] >= h[i]) left--;
 
    while(right < n && h[right+1] >= h[i]) right++;
 
    area = (right - left + 1) * h[i];
 
    if (area > res) res = area;
 
  }
 
  printf("%lld\n",res);
 
  return 0;
 
}

Реализация за O(n2) если что
Я эту тему уже создавал, но создал не в С++ для начинающих, а просто с++ поэтому решил тут сделать, а удалить не могу

@Pvt · 30.07.2019, 08:54

ссылка где проверяют?

@Bluestick · 30.07.2019, 09:06 **[ТС]**

https://informatics.mccme.ru/m... d=113915#1

@kitsoRik · 30.07.2019, 09:11

Bluestick, в данном случае, площать самого большого прямоугольника, это у прямоугольника у которого самая большая высота, что за базовая линия?

Добавлено через 3 минуты

Сообщение от Bluestick

Примеры
входные данные
7 2 1 4 5 1 3 3
выходные данные
8

Почему тут 8? Разве 7*1 не будет 7?

@Bluestick · 30.07.2019, 09:20 **[ТС]**

с чего вы взяли что 7? Прямоугольник должен быть на общей базовой черте
(в ссылке есть задача Гистограмма, а в ней рисунок как только посмотрите поймете)

@XLAT · 30.07.2019, 09:24

Сообщение от kitsoRik

Почему тут 8? Разве 7*1 не будет 7?

Сообщение от Bluestick

В первой строке входного файла записано число N (0 < N ≤ 10^6) - количество прямоугольников гистограммы.

7 это кол-во прямоугольников.
ответ должен быть 5.

Добавлено через 2 минуты

Сообщение от Bluestick

в ссылке есть задача Гистограмма

Сообщение от Bluestick

https://informatics.mccme.ru/mod/sta...terid=113915#1

это реклама?
чтобы 2 секунды посмотреть на вашу гистограмму мне надо 20 минут потратить на регистрацию?

@kitsoRik · 30.07.2019, 09:24

Bluestick, там вход по кодовому слову

Сообщение от XLAT

7 это кол-во прямоугольников.
ответ должен быть 5.

тут да, незаметил, всегда же делают перевод что бы отделить, хорошо, но ответ то не совпал

@Bluestick · 30.07.2019, 09:25 **[ТС]**

ну смотрите, 7 - это просто столб (т.к у него ширина 1, а нам нужен прямоугольник) рядом с ним стоит столб в высотой 2 и получается прямоугольник 2 на 2. Это и есть базовая черта
Попробуйте в paint нарисован примерно и тогда поймете

@Pvt · 30.07.2019, 09:27

региться еще по этой ссылке, сами проверяйте

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int h[1000000]={7, 2, 1, 4, 5, 1, 3, 3};
void main(int argc,char **argv)
{
    int n=8;
    scanf("%d",&n);
    for(int i = 0; i < n; i++)
        scanf("%d",h+i);
    int left, right, old;
    long long area, res=0;
    for(int i = 0; i < n; i++)
    {
        left = right = i;
        int hi=h[i];
        if(i)
        {
            if(hi==h[i-1]) continue;
            if(hi<h[i-1]) left=old;
        }
        while(left && h[left-1] >= hi) left--;
        while(right < n-1 && h[right+1] >= hi) right++;
        area = (right - left + 1ll) * hi;
        if (area > res) res = area;
        old=left;
    }
    cout<<res<<endl;

@Bluestick · 30.07.2019, 09:27 **[ТС]**

главное понимать что нам нужны именно прямоугольники, а не столбы

@kitsoRik · 30.07.2019, 09:27

Bluestick, Гистограмма

Сообщение от Bluestick

это просто столб (т.к у него ширина 1, а нам нужен прямоугольник)

столб не прямоугольник? У него в любом случае есть высота и ширина,

Сообщение от Bluestick

2 на 2

2 на 2? Так ширина же всегда 1.

@Bluestick · 30.07.2019, 09:35 **[ТС]**

Они соединяются столбы что дают во входных прилипают друг к другу от того и получается что

Сообщение от Bluestick

4 5

ихняя площадь больше чем площадь 5

Добавлено через 39 секунд
ошибка компиляции
(в начале коде я добавлял #include <iostream> using namespace std; так что не из-за этого)

@XLAT · 30.07.2019, 09:40

Сообщение от Bluestick

Попробуйте в paint нарисован примерно и тогда поймете

всё по инструкции:

Сообщение от Bluestick

ну смотрите, 7 - это просто столб (т.к у него ширина 1, а нам нужен прямоугольник) рядом с ним стоит столб в высотой 2 и получается прямоугольник 2 на 2. Это и есть базовая черта

прямоугольник 2 на 2 является чертой?

@Bluestick · 30.07.2019, 09:41 **[ТС]**

именно так

@Pvt · 30.07.2019, 09:43

Сообщение от Bluestick

ошибка компиляции

main закрыт }?

@Bluestick · 30.07.2019, 10:09 **[ТС]**

Сообщение от Pvt

void main(int argc,char **argv)

про это? Если закрою хуже станет

@Pvt · 30.07.2019, 10:16

..... стр.26 = }

@Bluestick · 30.07.2019, 12:13 **[ТС]**

что значит стр 26?

@kitsoRik · 30.07.2019, 12:41

Сообщение от Bluestick

что значит стр 26?

строка

@Bluestick · 30.07.2019, 13:38 **[ТС]**

005215.cpp:4:32: error: '::main' must return 'int'
void main(int argc, char **argv)
видимо ошибка на уровне входных данных
(я не могу запустить код, ибо с++ недавно сломался и не хочет запускать коды)

Новые блоги и статьи Все статьи Все блоги /
Доступность команды формы по условию Maks 07.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: сделать доступной кнопку (команда формы "ЗавершитьСписание") при. . .	Уведомление о неверно выбранном значении справочника Maks 06.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "НарядПутевка", разработанного в конфигурации КА2. Задача: уведомлять пользователя, если в документе выбран неверный склад. . .	Установка Qt Creator для C и C++: ставим среду, CMake и MinGW без фреймворка Qt 8Observer8 05.04.2026 Среду разработки Qt Creator можно установить без фреймворка Qt. Есть отдельный репозиторий для этой среды: https:/ / github. com/ qt-creator/ qt-creator, где можно скачать установщик, на вкладке Releases:. . .	AkelPad-скрипты, структуры, и немного лирики.. testuser2 05.04.2026 Такая программа, как AkelPad существует уже давно, и также давно существуют скрипты под нее. Тем не менее, прога живет, периодически что-то не спеша дополняется, улучшается. Что меня в первую очередь. . .
Отображение реквизитов в документе по условию и контроль их заполнения Maks 04.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеСпецтехники", разработанного в конфигурации КА2. Данный документ берёт данные из другого нетипового документа. . .	Фото всей Земли с борта корабля Orion миссии Artemis II kumehtar 04.04.2026 Это первое подобное фото сделанное человеком за 50 лет. Снимок называют новым вариантом легендарной фотографии «The Blue Marble» 1972 года, сделанной с борта корабля «Аполлон-17». Новое фото. . .	Вывод диалогового окна перед закрытием, если документ не проведён Maks 04.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: реализовать программный контроль на предмет проведения документа. . .	Программный контроль заполнения реквизитов табличной части документа Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: 1. Реализовать контроль заполнения реквизита. . .

@Pvt Заблокирован
	30.07.2019, 08:54
	ссылка где проверяют? 0

@Bluestick 0 / 0 / 0 Регистрация: 15.07.2019 Сообщений: 69
	30.07.2019, 09:06 [ТС]
	https://informatics.mccme.ru/m... d=113915#1 0

@Bluestick 0 / 0 / 0 Регистрация: 15.07.2019 Сообщений: 69
	30.07.2019, 09:20 [ТС]
	с чего вы взяли что 7? Прямоугольник должен быть на общей базовой черте (в ссылке есть задача Гистограмма, а в ней рисунок как только посмотрите поймете) 0

@Bluestick 0 / 0 / 0 Регистрация: 15.07.2019 Сообщений: 69
	30.07.2019, 09:25 [ТС]
	ну смотрите, 7 - это просто столб (т.к у него ширина 1, а нам нужен прямоугольник) рядом с ним стоит столб в высотой 2 и получается прямоугольник 2 на 2. Это и есть базовая черта Попробуйте в paint нарисован примерно и тогда поймете 0

@Bluestick 0 / 0 / 0 Регистрация: 15.07.2019 Сообщений: 69
	30.07.2019, 09:27 [ТС]
	главное понимать что нам нужны именно прямоугольники, а не столбы 0

@Bluestick 0 / 0 / 0 Регистрация: 15.07.2019 Сообщений: 69
	30.07.2019, 09:41 [ТС]
	именно так 0

@Pvt Заблокирован
	30.07.2019, 10:16
	..... стр.26 = } 0

@Bluestick 0 / 0 / 0 Регистрация: 15.07.2019 Сообщений: 69
	30.07.2019, 12:13 [ТС]
	что значит стр 26? 0

@Bluestick 0 / 0 / 0 Регистрация: 15.07.2019 Сообщений: 69
	30.07.2019, 13:38 [ТС]
	005215.cpp:4:32: error: '::main' must return 'int' void main(int argc, char **argv) видимо ошибка на уровне входных данных (я не могу запустить код, ибо с++ недавно сломался и не хочет запускать коды) 0