Подсчет количества элементов в структуре данных из текущего индекса справа налево и печать количества для каждого элемента - PullRequest
Новая
       28

Подсчет количества элементов в структуре данных из текущего индекса справа налево и печать количества для каждого элемента

0 голосов
/ 02 июня 2019

В городе имеются различные сигнальные башни. Башни выровнены по прямой горизонтальной линии (слева направо), и каждая башня передает сигнал справа налево. Башня А должна блокировать сигнал Башни В, если Башня A присутствует слева от Башни B, а Башня A выше Башни B. Таким образом, диапазон сигнала данной башни может быть определен как:

{(количество смежных башен слева от данной башни, высота которых меньше или равна высоте данной башни) + 1}. 

#include <iostream>
#include <vector>
using namespace std;
vector<int> res;
void recursion(int a[],int x)
{
if (x >= 0)
{// Taking the last element of the array as the max element
    int max = a[x], count = 0;
    for (int i = x; i >= 0; i--)
    {//Comparing the max with all the elements in the array
        if (max >= a[i])
        {
            count++;
        }
        else
        {
            break;
        }
    }
    //Pushing the count of the current element in the vector.
    res.push_back(count);
    x = x - 1;
    recursion(a, x);
}
}
    int main() {
int TestCase, n;
cin >> TestCase;
for (int l = 0; l < TestCase; l++)
{
    cin >> n;
    int * arr = new int[n];
    //Getting the elements
    for (int j = 0; j < n; j++)
    {
        cin >> arr[j];
    }
    recursion(arr, n-1);
    //Iterating through the vector in reverse manner and printing 
            //the result.
    for (auto it = res.rbegin(); it != res.rend(); ++it)
    {
        cout << *it << " ";
    }
    delete[] arr;
}
return 0;
}

Первая строка содержит целое число T, указывающее количество тестовых случаев.

Вторая строка содержит целое число n, указывающее количество башен.

Третья строка содержит n целых чисел, разделенных пробелом (H [i]), обозначающих высоту каждой башни.

Печать диапазона каждой башни (разделенного пробелом).

Пример ввода : 

1
7
100 80 60 70 60 75 85

Пример вывода : 

1 1 1 2 1 4 6

Мое решение верное, но проблема заключается в сложности времени. Есть ли способ уменьшить сложность времени?

1 Ответ

1 голос
/ 02 июня 2019

  • Для расчета дальности каждой башни, которая излучает сигналы влево, вам необходимо использовать структуру stack.

  • Мы переходим от слева направо в массиве и сохраняем каждый элемент в стеке. Теперь мы вставляем башни в стек.

  • Всякий раз, когда мы добираемся до следующей башни, мы продолжаем выскакивать башни из стека, высота которого меньше текущей башни. После этого мы вставим текущую башню в стек и так далее для последующих башен.

  • Важная вещь , на которую следует обратить внимание, это то, что вам нужно будет хранить номер. башен, побитых текущей башней, когда вы вставляете их в стек.

  • Ответ для каждой башни (кроме базового варианта) - нет. башен избит + 1.

  • Целое число внутри {} ниже - это номер. башен, побитых нынешней башней.

Пример: 

100 80 60 70 60 75 85
 ^
  • Стек пуст, когда мы находимся на 100, поэтому мы вставляем его в стек и печатаем ответ для него как 1, считая это базовым ответом. 
Current stack: 100{0}
80 60 70 60 75 85
^
  • Теперь давайте проверим на 80. Когда башня 80 испускает сигналы влево, мы продолжаем изматывать все элементы из стека, которые меньше 80, и останавливаемся, когда получаем блок (то есть башня с такой же или большей высотой). В этом случае мы останавливаемся на 100. Таким образом, расстояние, пройденное сигналом, составляет 1. 
Current stack: 100{0} 80{0}
60 70 60 75 85
^
  • Теперь, ответ для 60 снова 1. 
Current stack: 100{0} 80{0} 70{1}
70 60 75 85
^
  • Для 70 сигналы бьют 60 и останавливаются на 80, поэтому ответ для 70 - нет. башен побито + 1, поэтому 1 + 1 = 2. 
Current stack: 100{0} 80{0} 70{1} 60{0}
60 75 85
^
  • 60 никого не бьет, поэтому 0 + 1 = 1. 
Current stack: 100{0} 80{0} 75{3}
75 85
^
  • 75 бьет 60 и 70, но мы получаем 3 башен, поскольку мы добавляем no. башен, побитых меньшими башнями + и сама эта башня. Итак, проще говоря,

60 {0} равно 1 (само 60) + 0 (количество башен, побитых самой 60) + 1 (само 70) + 1 (количество башен, побитых самой 70) = 1 + 1 + 1 = 3. Ответ для 75 - 3 + 1 = 4. 

Current stack: 100{0} 85{5}
85
^
  • Ответ для 85: 5 + 1 = 6 => 1 (из 75) + 3 (из 75 ударов) + 1 (из 80) + 0 (из 80 ударов).

Надеюсь, это ответит на ваш вопрос.

...