Решал задачу и тут у меня получился 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<<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;
}
Полный текст задачи:
Лайнландия представляет из себя одномерный мир, являющийся прямой, на котором располагаются N городов, последовательно пронумерованных от 0 до N - 1 . Направление в сторону от первого города к нулевому названо западным, а в обратную - восточным.
Когда в Лайнландии неожиданно начался кризис, все были жители мира стали испытывать глубокое смятение. По всей Лайнландии стали ходить слухи, что на востоке живётся лучше, чем на западе. Так и началось Великое Лайнландское переселение. Обитатели мира целыми городами отправились на восток, покинув родные улицы, и двигались до тех пор, пока не приходили в город, в котором средняя цена проживания была меньше, чем в родном.