I solved the problem and then I got time_lim, I need to optimize this algorithm so that it passes 2 tests, not enough 4-5 ms. The algorithm searches for the first occurrence of an element that is not greater than the i-th and its index is greater than i, if it does not output -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<<j<<' '; return true; } return false; } void fun(int n) { ++i; n1=n; it=find_if(v.begin()+i,v.end(),perd); if(it==v.end()) cout<<-1<<' '; j=i; } void funcin(int &n) { cin>>n; } int main() { cin >> n1; v.resize(n1); for_each(v.begin(),v.end(),funcin); for_each(v.begin(),v.end(),fun); return 0; }

Full text of the problem:

Lineland is a one-dimensional world, which is a straight line, on which are located N cities, sequentially numbered from 0 to N - 1. The direction away from the first city to zero is called western, and in the opposite direction - eastern.

When the crisis suddenly began in Linelandia, everyone in the world began to experience deep confusion. Rumors circulated throughout Linelandia that they lived better in the east than in the west. Thus began the Great Lineland Relocation. The inhabitants of the world went to the east by whole cities, having left their native streets, and moved until they came to a city in which the average price of living was less than in their own.

  • one
    you have a quadratic complexity algorithm, this is usually slow. Is it possible to show the original wording of the problem? - KoVadim

1 answer 1

Your quadratic complexity algorithm. I’ve just come up with an interesting algorithm for solving this problem, it has to be very fast, it’s linear:

We will use a stack of numbers (a simple vector in which you can add and remove an element from the end). The essence of the algorithm is that we find areas with a strict growth of elements, if the area is suddenly interrupted, i.e. suddenly the element is less than the previous element, then it is possible to assign the end part of the previous ascending section to all that this element is the nearest smaller of them all. Those. Here is the algorithm - we move along the array from left to right, while checking that while there is a larger (current) element at the top of the stack and the stack is not empty, then we displace the element from the stack and assign this element (stack) to it that the closest element to it is our observed array element . In the end, if the stack is not empty, then we assign to all its elements that a suitable element is not found for them. set -1. You may notice that there is always a loosely increasing sequence in the stack.

This algorithm is linear (relative to the size of the array N), since it passes through all the elements of the array exactly once and at the same time it makes no more than N additions and displacements and 2 * N comparisons from the stack. Here is the full algorithm in C ++ (run online in C ++ and in Python ):

 #include <iostream> #include <vector> using namespace std; int main() { // nums - входные числа, stck - стэк, result - ответ vector<int> 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; }
  • My answer does not work when the input data is 1 2 3 2 1 4 2 5 3 1 it should give -1 4 3 4 -1 6 9 8 9 -1, and your variant yields 4 3 3 4 9 6 9 8 9 -1 - Paul Shipilov
  • but I understood your idea, I will try to implement it, if it's not difficult to finish your code all the time, so that if I understand where I’m pierced. And why would you use vectoe "stack" if you have a wonderful stack container in STL? - Paul Shipilov
  • one
    @PaulShipilov on your input data the answer is different for me, because You wrote at the beginning that you need to find numbers that are “not greater than” the current one, and in your code you used “strictly less”. Decide what you need. In my code, just while comparing do> instead of> =. By the way, write in your question the exact statement of the problem as it was given to you, also write test examples. - Arty OneSoul
  • @PaulShipilov I tried your test case by replacing my while> = with> and received exactly your answer. When you decide what exactly is required, I could correct the code. - Arty OneSoul
  • I already noticed and corrected, thank you very much for the good algorithm, maybe someday I will move away from the square one and switch to linear ones) - Paul Shipilov