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

Гистограмма

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

Здраствуйте, подскажите идею решения задачи, именно идею а не само решение, если это возможно.
Вот сылочка:
http://codeforces.com/group/Wv... /problem/D
Никак не могу придумить эффективное решение, котрое бы укладивалость в оведенное время. Спасибо.
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
08.03.2018, 15:01
Ответы с готовыми решениями:

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

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

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

Гистограмма
#pragma once #include <stdlib.h> namespace gist { using namespace System; using namespace...

7
193 / 173 / 30
Регистрация: 10.07.2012
Сообщений: 800
10.03.2018, 20:48 2
можно перебрать позицию, в которой будет находиться самый низкий столбик из той группы, которая войдет в ответ. для каждого такого нужно определить максимальный отрезок вокруг него, где все столбики будут не ниже. и обновить ответ получившимся. этап "определить максимальный отрезок..." можно реализовать с помощью мини-динамики или стека.
0
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
Модератор
2959 / 2098 / 450
Регистрация: 26.03.2015
Сообщений: 8,148
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
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
Модератор
2959 / 2098 / 450
Регистрация: 26.03.2015
Сообщений: 8,148
11.03.2018, 21:35 6
Цитата Сообщение от Andrey_lev Посмотреть сообщение
Не пойму почему трюк с добавлением фиктивных элементов в начало и конец массива исполнен некорректно, ведь по умолчанию значения в векторе устанавливаются в ноль.
Попробуйте входные данные "2 0 2".

Добавлено через 30 секунд
высоты прямоугольников (0 ≤ hi ≤ 109)
0
1 / 1 / 0
Регистрация: 25.09.2016
Сообщений: 6
11.03.2018, 21:55  [ТС] 7
Да как-то я не подумал, что при нуле из пустого стека будут удаляться элементы, спасибо.
Ошибку не трудно устранить, изменив фиктивные элементы, но очень странно что решение было принято.
0
Модератор
2959 / 2098 / 450
Регистрация: 26.03.2015
Сообщений: 8,148
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
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
12.03.2018, 10:10
Помогаю со студенческими работами здесь

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

Гистограмма
Подобрать такой числовой ряд 0-100, чтобы гистограмма выравнивалась экспонентом. Гистограмму я...

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

гистограмма
помогите сделать легенду и чтобы квадратики были широкие uses crt; Var a,b:array of byte; ...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru