0 / 0 / 0
Регистрация: 15.07.2019
Сообщений: 67
1

Гистограмма (превышен лимит времени)

26.07.2019, 11:51. Показов 2612. Ответов 6
Метки нет (Все метки)

Гистограмма является многоугольником, сформированным из последовательности прямоугольников, выровненных на общей базовой линии. Прямоугольники имеют равную ширину, но могут иметь различные высоты. Например, фигура слева показывает гистограмму, которая состоит из прямоугольников с высотами 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

Вот код:
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;
 
}
Но он не проходит 1 тест (превышено время ожидания)
Помогите оптимизировать код пожалуйста
0

Помощь в написании контрольных, курсовых и дипломных работ здесь.

Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
26.07.2019, 11:51
Ответы с готовыми решениями:

Лимит по времени
Как можно сделать еще быстрее? Время работы 1.046 сек. Хотелось бы меньше 1.00 секунды:) ...

Просрочен лимит времени
Я решал задачу, вот она: Проблема в том, что я когда заносил в массив данные через scanf, то она...

Счастливый билет (Лимит Времени)
Всем привет! Контестер пишет Time Limit. Подскажите что можно сделать чтоб моя программа работала...

Превышен лимит символов
Ситуация такая. Добавляю в бд записи, хочу их удалить, но вместо удаления вылазит такое. Читал,...

6
357 / 224 / 120
Регистрация: 25.06.2019
Сообщений: 828
26.07.2019, 14:06 2
если h[i]<h[i-1](если равен площади совпадут), то можно воспользоваться area[i-1], ну зная right[i-1] и left[i-1] есс-но
0
0 / 0 / 0
Регистрация: 15.07.2019
Сообщений: 67
29.07.2019, 07:55  [ТС] 3
если честно, не особо понял как мне воспользоваться area[i-1]
0
357 / 224 / 120
Регистрация: 25.06.2019
Сообщений: 828
29.07.2019, 08:48 4
она пожалуй ни к чему, предыдущий left будет начальным, а не i
0
0 / 0 / 0
Регистрация: 15.07.2019
Сообщений: 67
29.07.2019, 10:13  [ТС] 5
так как все таки оптимизировать код?
0
6 / 10 / 2
Регистрация: 08.08.2019
Сообщений: 63
02.09.2019, 15:56 6
Bluestick Так превышен TL или время ожидания? Ты уже определись.
0
бах-бах и в продакшен!
2988 / 1605 / 564
Регистрация: 23.09.2014
Сообщений: 4,959
Записей в блоге: 4
06.09.2019, 11:08 7
hacthies, афтор уже получил годный ответ по этой теме:
Нужно оптимизировать код
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
06.09.2019, 11:08

Помощь в написании контрольных, курсовых и дипломных работ здесь.

Превышен временной лимит
Здравствуйте! Помогите пож-ста разобраться... Написал программу #include &lt;stdio.h&gt; #include...

Превышен Лимит Поля В 32кб
Вопрос наверное уже такой был, но ответа найти не могу. В текстовом поле объем данных превысил 32...

Ошибка загрузки аудиофайла на сервер (превышен лимит)
Почему появляется ошибка: Warning: POST Content-Length of 9096399 bytes exceeds the limit of...

Ошибка "превышен лимит памяти" при сдаче программы на сайте Олимпиады
Здравствуйсте, помогите пожалуйста! Решил олимпиадную задачу, у меня на моем Ubuntu 14.04 + Geany...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
7
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.