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

C++

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

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

12.07.2017, 19:04. Просмотров 168. Ответов 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].

Как это сделать за ЛИНЕЙНОЕ ВРЕМЯ?
Лучшие ответы (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 — количество особых элементов массива А, считая его элемент особым, если он больше суммы...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Почтальон
Модератор
361 / 283 / 50
Регистрация: 22.03.2015
Сообщений: 2,221
Завершенные тесты: 1
13.07.2017, 07:37 #2
Цитата Сообщение от Aleksey19718 Посмотреть сообщение
ЛИНЕЙНОЕ ВРЕМЯ?
Может быть это значит заполнять массив за определенное время через одинаковый промежуток времени ?
oldnewyear
304 / 286 / 90
Регистрация: 21.05.2016
Сообщений: 884
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;
}
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,добавить еденицу.


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

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

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