Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Andrey_lev
1 / 1 / 0
Регистрация: 25.09.2016
Сообщений: 6
1

Гистограмма

08.03.2018, 15:01. Просмотров 223. Ответов 7
Метки нет (Все метки)

Здраствуйте, подскажите идею решения задачи, именно идею а не само решение, если это возможно.
Вот сылочка:
http://codeforces.com/group/WvBzg1XcCv/contest/220783/problem/D
Никак не могу придумить эффективное решение, котрое бы укладивалость в оведенное время. Спасибо.
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.03.2018, 15:01
Ответы с готовыми решениями:

Гистограмма
Доброе утро, граждане. Мне нужно сделать гистограмму, как ее строить? Нашел...

Гистограмма
Дано предложение.Нарисовать вертикальную гистограмму символов этого предложения.

Гистограмма
Программирую на C# использую VS 2008 Для моей программы нужно построить...

Гистограмма
Здравствуйте, помогите,пожалуйста, разобраться! Есть гистограмма. Как мне...

Гистограмма
Всем доброго времени суток, подскажите есть ли в питоне средства для создания...

7
salam
182 / 163 / 29
Регистрация: 10.07.2012
Сообщений: 775
10.03.2018, 20:48 2
можно перебрать позицию, в которой будет находиться самый низкий столбик из той группы, которая войдет в ответ. для каждого такого нужно определить максимальный отрезок вокруг него, где все столбики будут не ниже. и обновить ответ получившимся. этап "определить максимальный отрезок..." можно реализовать с помощью мини-динамики или стека.
0
Andrey_lev
1 / 1 / 0
Регистрация: 25.09.2016
Сообщений: 6
11.03.2018, 00:31  [ТС] 3
Спасибо за подсказку. Задачу я уже решил вот таким способом

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
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
 
int main() {
    std::ios_base::sync_with_stdio(false);
    int N;
    std::cin >> N;
 
    std::vector<int> h(N + 2);
    for (int i = 1; i <= N; ++i)
        std::cin >> h[i];
 
    long long out = 0;
    std::vector<long long> r(N);
    std::stack<int> s1, s2;
    s1.push(0); s2.push(N + 1);
    for (int i = 1; i <= N; ++i) {
        while (h[s1.top()] >= h[i]) {
            s1.pop();
        }
        while (h[s2.top()] >= h[N - i + 1]) {
            s2.pop();
        }
        
        r[i - 1] += ((long long)i - (long long)s1.top()) * (long long)h[i];
        r[N - i] += ((long long)s2.top() - (long long)(N - i + 1) - 1LL) * (long long)h[N - i + 1];
        
        if (i > N / 2)
            out = std::max(std::max(r[i - 1], r[N - i]), out);
        
        s1.push(i);
        s2.push(N - i + 1);
    }
    std::cout << out;
}
1
Shamil1
Модератор
2234 / 1522 / 346
Регистрация: 26.03.2015
Сообщений: 5,428
11.03.2018, 20:50 4
Цитата Сообщение от Andrey_lev Посмотреть сообщение
Задачу я уже решил вот таким способом
И что, неужели проходит все тесты?

Добавлено через 14 минут
Идея алгоритма понятна, но...
1. Меня смущают Ваши манипуляции с r меня смущают. Мне показалось, что в какой-то момент Вы к значениям, полученным при проходе слева направо Вы прибавляете значения, полученные при проходе справа налево. Тем более, что сама логика алгоритма вообще не требует сохранения этих значений.
2. Ваш трюк с добавлением фиктивных элементов в начало и конец массива исполнен некорректно.

Добавлено через 2 часа 9 минут
С первым вопросом я разобрался.

Добавлено через 5 минут
По второму вопросу - видимо, чтобы исправить, достаточно присвоить:
C++
1
2
    h[0] = -1;
    h[n+1] = -1;
0
Andrey_lev
1 / 1 / 0
Регистрация: 25.09.2016
Сообщений: 6
11.03.2018, 21:19  [ТС] 5
Да проходит все тесты.
Попытаюсь объяснить. В данной строке:
C++ (Qt)
1
r[i - 1] += ((long long)i - (long long)s1.top()) * (long long)h[i];
я вычисляю площадь прямоугольника, который можно поместить от i-ого столбца, до первого меньшего слева - s1.top(), а в строке:
C++ (Qt)
1
r[N - i] += ((long long)s2.top() - (long long)(N - i + 1) - 1LL) * (long long)h[N - i + 1];
вычисляю площадь прямоугольника, который можно поместить от (N - i + 1)-ого столбца, до первого меньшего справа - s2.top(), вычитая при это единицу, чтобы не прибавлять площадь i-го столбца дважды. И когда i > N / 2 в массиве r появляются значения для определенных столбцов.

Не пойму почему трюк с добавлением фиктивных элементов в начало и конец массива исполнен некорректно, ведь по умолчанию значения в векторе устанавливаются в ноль.
0
Shamil1
Модератор
2234 / 1522 / 346
Регистрация: 26.03.2015
Сообщений: 5,428
11.03.2018, 21:35 6
Цитата Сообщение от Andrey_lev Посмотреть сообщение
Не пойму почему трюк с добавлением фиктивных элементов в начало и конец массива исполнен некорректно, ведь по умолчанию значения в векторе устанавливаются в ноль.
Попробуйте входные данные "2 0 2".

Добавлено через 30 секунд
высоты прямоугольников (0 ≤ hi ≤ 109)
0
Andrey_lev
1 / 1 / 0
Регистрация: 25.09.2016
Сообщений: 6
11.03.2018, 21:55  [ТС] 7
Да как-то я не подумал, что при нуле из пустого стека будут удаляться элементы, спасибо.
Ошибку не трудно устранить, изменив фиктивные элементы, но очень странно что решение было принято.
0
Shamil1
Модератор
2234 / 1522 / 346
Регистрация: 26.03.2015
Сообщений: 5,428
12.03.2018, 10:10 8
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
a = list(map(int, '2 1 4 5 1 3 3'.split()))
 
def solve(a):
    s = [(0,-1)]
    def f(i,x):
        while s[-1][1] >= x:
            s.pop()
        s.append((i+1,x))
        return (i - s[-2][0])*x
    r = [f(i,x) for i,x in enumerate(reversed(a))]
    s = [(0,-1)]
    return max(f(i,x) + x + r[::-1][i] for i,x in enumerate(a))
 
print(solve(a))
Добавлено через 39 минут
ИМХО так наглядней.
Сначала вычисляем площади прямоугольников справа (r).
Затем вычисляем площади прямоугольников слева и сразу добавляем к ним площадь самой полоски (x) и площадь прямоугольника справа (r[::-1][i]).
0
12.03.2018, 10:10
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.03.2018, 10:10

Гистограмма
Пожалуйста помогите! Мне срочно нужно написать программу которая считывает...

гистограмма
помогите сделать легенду и чтобы квадратики были широкие uses crt; Var...

Гистограмма
Помогите, есть задача: с клавиатуры вводится число n &lt; 20, заполнить массив...


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

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

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