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

@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)
видимо ошибка на уровне входных данных
(я не могу запустить код, ибо с++ недавно сломался и не хочет запускать коды)

Новые блоги и статьи Все статьи Все блоги /
Знаешь почему 90% людей редко бывают счастливыми? kumehtar 14.04.2026 Потому что они ждут. Ждут выходных, ждут отпуска, ждут удачного момента. . . а удачный момент так и не приходит.	Фиксация колонок в отчете СКД Maks 14.04.2026 Фиксация колонок в СКД отчета типа Таблица. Задача: зафиксировать три левых колонки в отчете. Процедура ПриКомпоновкеРезультата(ДокументРезультат, ДанныеРасшифровки, СтандартнаяОбработка) / / . . .	Настройки VS Code Loafer 13.04.2026 { "cmake. configureOnOpen": false, "diffEditor. ignoreTrimWhitespace": true, "editor. guides. bracketPairs": "active", "extensions. ignoreRecommendations": true, . . .	Оптимизация кода на разграничение прав доступа к элементам формы Maks 13.04.2026 Алгоритм из решения ниже реализован на нетиповом документе, разработанного в конфигурации КА2. Задачи, как таковой, поставлено не было, проделанное ниже исключительно моя инициатива. Было так:. . .
Контроль заполнения и очистка дат в зависимости от значения перечислений Maks 12.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: реализовать контроль корректности заполнения дат назначения. . .	Архитектура слоя интернета для сервера-слоя. Hrethgir 11.04.2026 В продолжение https:/ / www. cyberforum. ru/ blogs/ 223907/ 10860. html Знаешь что я подумал? Раз мы все источники пишем в голове ветки, то ничего не мешает добавить в голову такой источник, который сам. . .	Подстановка значения реквизита справочника в табличную часть документа Maks 10.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: при выборе сотрудника (справочник Сотрудники) в ТЧ документа. . .	Очистка реквизитов документа при копировании Maks 09.04.2026 Алгоритм из решения ниже применим как для типовых, так и для нетиповых документов на самых различных конфигурациях. Задача: при копировании документа очищать определенные реквизиты и табличную. . .

@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