Оптимизация алгоритма поиска первого вхождения элемента который не больше i-ого и его индекс больше i

#cpp #vector

Решал задачу и тут у меня получился time_lim, мне нужно оптимизировать этот алгоритм,
чтоб он прошел 2 теста, не хватает 4-5 мс. Алгоритм ищет первое вхождения элемента
который не больше i-ого и его индекс больше i, если его нет выводит -1.

 int i(0),j(0);
 int n1;
 v_t v;  //вектор типа int
 auto it(v.begin());

bool perd(int n)
{
    ++j;
    if(n1>n)
    {
        cout<>n;
}

int main()
{
    cin >> n1;
    v.resize(n1);
    for_each(v.begin(),v.end(),funcin);
    for_each(v.begin(),v.end(),fun);
    return 0;
}


Полный текст задачи:


  Лайнландия представляет из себя одномерный мир, являющийся прямой, на котором располагаются
N городов, последовательно пронумерованных от 0 до N - 1 . Направление в сторону от
первого города к нулевому названо западным, а в обратную - восточным. 
  
  Когда в Лайнландии неожиданно начался кризис, все были жители мира стали испытывать
глубокое смятение. По всей Лайнландии стали ходить слухи, что на востоке живётся лучше,
чем на западе. Так и началось Великое Лайнландское переселение. Обитатели мира целыми
городами отправились на восток, покинув родные улицы, и двигались до тех пор, пока
не приходили в город, в котором средняя цена проживания была меньше, чем в родном.

    

Ответы

Ответ 1

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

Мы будем использовать стэк из чисел (простой вектор в который можно добавить и убрать
с конца элемент). Суть алгоритма в том что мы находим участки со строгим возрастанием
элементов, если участок вдруг прерывается, т.е. вдруг элемент меньше предыдущего элемента,
тогда можно концевой части предыдущего возрастающего участка всем назначить что этот
элемент ближайший меньший их всех. Т.е. вот алгоритм - движемся по массиву слева направо,
при этом проверяем что пока в вершине стэка находится больший (текущего) элемент и
стэк не пуст, то вытесняем из стэка элемент и назначаем этому элементу (стэковому)
что ближайший к нему искомый это наш наблюдаемый элемент массива. В конце если стэк
не пуст то всем его элементам назначаем что не найдено для них подходящего элемента
т.е. ставим -1. Можно заметить что в стэке всегда находится нестрого возрастающая последовательность.

Такой алгоритм линейный (относительно размера массива N), т.к. он проходит по всем
элементам массива ровно один раз и при этом из стэка делает не больше N добавлений
и вытеснений и 2*N сравнений. Вот полный алгоритм на C++ (запустить онлайн на C++ и
на Python):

#include 
#include 
using namespace std;

int main() {
    // nums - входные числа, stck - стэк, result - ответ
    vector nums, stck, result;

    // Заполняем входной массив, можно через std::cin.
    nums = {1,2,3,2,1,4,2,5,3,1}; // Выдаёт -1 4 3 4 -1 6 9 8 9 -1
    result.resize(nums.size(), -1);

    // Основной алгоритм.
    for (size_t i = 0; i < nums.size(); ++i) {
        while (!stck.empty() && nums[stck.back()] > nums[i]) {
            result[stck.back()] = i;
            stck.pop_back();
        }
        stck.push_back(i);
    }

    // Выводим результат.
    for (size_t i = 0; i < result.size(); ++i) {
        cout << result[i] << " ";
    }

    return 0;
}