Использование std::find_if для массива (STL)

271

28 июня 2017, 00:01

Мне необходимо обработать массив и выявить индекс элемента, значение которого меньше определенного(Если таких элементов несколько, то узнать первое появление).

Я сделал примерно так:

#include <iostream>
using namespace std;
int main()
{
    int N; cin >> N;
    int A[N];
    int total[N];
    for(int i = 0; i < N; i++)
    {
        cin >> A[i];
        total[i] = -1;
    }
    for(int i = 0; i < N; i++)
    {
        for(int j = i; j < N; j++)
        {
            if(A[i] > A[j])
            {
                total[i] = j;
                break;
            }
        }
    }
    for(int i = 0; i < N; ++i)
    {
        cout << total[i] << " ";
    }
    return 0;
}

У меня два вопроса:

Как сделать такой алгоритм быстрее?

Можно ли реализовать что-то подобное с помощью std::find_if?

Сама задача: http://informatics.mccme.ru/moodle/mod/statements/view.php?chapterid=112736#1

Программа валится на двух тестах и именно из-за скорости выполнения.

Answer 1

Непонятно, зачем вам O(N^2)? и вообще что вы делаете - у вас нет никакого определенного значения. Если оно - M, то достаточно

int i = 0;
for(;i<N;++i) if (A[i] < M) break;

Все. Если i меньше N - это искомый индекс, если равно N - такого элемента нет.

С find_if:

int* res = find_if(A,A+N,[](int a){return a < M; });

res указывает на искомый элемент. Если res указывает за пределы A - на A[N] - такого элемента нет.

Но - еще раз! Вы явно неверно сформулировали задачу! А я отвечаю на строго ваш вопрос - выявить индекс элемента, значение которого меньше определенного.

P.S. Ага, глянул исходную задачу. Вы по сути вместо того чтоб спросить, как удобнее забить гвоздь, спросили - как удобнее держать микроскоп при забивании гвоздя... Я ответил, соответственно, что микроскоп лучше держать за ручку, но ничего не рассказал про молоток :) Попробуйте подумать не над ускорением вашего метода, а над другим методом.