Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

C++

Войти
Регистрация
Восстановить пароль
 
Aleksey19718
3 / 3 / 1
Регистрация: 20.12.2015
Сообщений: 47
#1

Для каждого элемента B[i] записать в L[i] количество элементов B[0..i-1], которые больше либо равны B[i] - C++

12.07.2017, 19:04. Просмотров 231. Ответов 2
Метки нет (Все метки)

Народ. Помогите пожалуйста. Голову сломал.
Дан массив B размера n. Надо заполнить массив L[n] за линейное время следующим образом:
для каждого элемента B[i] записать в L[i] количество элементов B[0..i-1], которые больше либо равны B[i].
Допустим мы имеем массив B
Код
{ 1, 3, 2, 1, 5 }
. Массив L должен выглядеть следующим образом -
Код
{ 0, 0, 1, 3, 0 }
.
В книге написано что надо использовать стек, а формулировка примерно такая:

Требуется за линейное время находить L. Так, при обработке очередного элемента i полоски в вершине стека, имеющие большую либо равную длину, считываются и удаляются, и тем самым формируется L[i].

Как это сделать за ЛИНЕЙНОЕ ВРЕМЯ?
0
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.07.2017, 19:04
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Для каждого элемента B[i] записать в L[i] количество элементов B[0..i-1], которые больше либо равны B[i] (C++):

Определить в матрице количество элементов, которые больше суммы остальных элементов его столбца - C++ Builder
Помогите, пожалуйста. Нужен алгоритм расчета особого элемента. Задача стоит такая: Дана матрица размером NxM. Определить k - количество...

После максимального элемента вставить 5 элементов, которые равны минимальному элементу контейнера - C++
задание. Использование шаблонов и классов и алгоритмов библиотеки stl Задание: после максимального элемента вставить 5 элементов,...

Подсчитать количество элементов массива с одинаковым местоположением, которые равны - C++
Даны два массива равной длины.Подсчитать количество элементов с одинаковым местоположением, которые: а) равны б)элемент первого массива...

Дано двузначное число, определить какая из цифр больше, либо они равны - C++
Ребята срочно, через пол часа сдать нужно. Помогите код нужен. Дано двузначное число N. Определить, какая из цифр больше, первая или...

Найти количество элементов массива,которые меньше либо равняются заданному числу - C++
Задан массив a(n).Найти количество элементов массива,которые либо равняются заданному числу m,либо меньше заданного числа m,и рассчитать их...

Определить количество элементов матрицы, которые больше суммы остальных элементов этого столбца - C++
Дана матрица А размером n х m. Определить k — количество особых элементов массива А, считая его элемент особым, если он больше суммы...

2
Почтальон
Модератор
385 / 312 / 57
Регистрация: 22.03.2015
Сообщений: 2,440
Завершенные тесты: 1
13.07.2017, 07:37 #2
Цитата Сообщение от Aleksey19718 Посмотреть сообщение
ЛИНЕЙНОЕ ВРЕМЯ?
Может быть это значит заполнять массив за определенное время через одинаковый промежуток времени ?
0
oldnewyear
331 / 317 / 95
Регистрация: 21.05.2016
Сообщений: 1,004
13.07.2017, 10:50 #3
Лучший ответ Сообщение было отмечено автором темы, экспертом или модератором как ответ
Цитата Сообщение от Почтальон Посмотреть сообщение
Может быть это значит заполнять массив за определенное время через одинаковый промежуток времени ?
Линейное время означает, что временная сложность алгоритма O(n)

Цитата Сообщение от Aleksey19718 Посмотреть сообщение
Как это сделать за ЛИНЕЙНОЕ ВРЕМЯ?
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
#include <iostream>
#include <stack>
 
const int n = 5;
 
int main()
{
    using namespace std;
 
    int B[n] = {1, 3, 2, 1, 5};
    int L[n] = {0};
    stack<int> st;
    
    for (int i = 0; i < n; ++i) 
    {
        while(!st.empty() && B[st.top()] >= B[i])
        {
            st.pop();
        }
        if (st.empty()) L[i] = i;
        else L[i] = i - st.top()-1;
        st.push(i);
    }
 
    for (int i = 0; i < n; ++i)
    {
        cout << L[i] << " ";
    }
    cout << endl;
}
1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.07.2017, 10:50
Привет! Вот еще темы с ответами:

Найти произведение элементов массива, которые больше его первого элемента - C++
Всем здраствуйте! Помогите пожайлуста написать код с помощью массивов. Задание - Найти произведение элементов , которые больше за первый...

Напечатать номера элементов, которые равны на единицу больше наименьшего элемента массива - Pascal
1)Задан одномерный массив C(N) (N&lt;=70). Напечатать номера элементов, которые равны на единицу больше наименьшего элемента массива, и...

Подсчитайте количество элементов массива, которые больше или равны 25 - Pascal ABC
Двумерный массив С из 4-х строк и 2-х столбцов задан при помощи генератора случайных чисел из интервала (целые числа) Подсчитайте...

Дан целочисельный массив из n элементов.В конец записи каждого элемента,которые больше числа 10,добавить еденицу. - Turbo Pascal
Дан целочисельный массив из n элементов.В конец записи каждого элемента,которые больше числа 10,добавить еденицу.


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

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

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