Salut,

Je suis sur un exercice CodinGames dont voici le sujet :

Et j'ai donc fait ce code :

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

/**
 * Auto-generated code below aims at helping you parse
 * the standard input according to the problem statement.
 **/
int main()
{
    int N;
    std::cin >> N; std::cin.ignore();
    
    std::vector<int> horsesPower;
    for (int i = 0; i < N; i++) {
        int Pi;
        std::cin >> Pi; std::cin.ignore();
        
        horsesPower.push_back(Pi);
    }
    
    int min = std::numeric_limits<int>::max();
    for (auto i = 0; i < N - 1; ++i)
    {
        for (auto j = i + 1; j < N; ++j)
        {
            int currentGap;
            if (horsesPower[i] > horsesPower[j])
                currentGap = horsesPower[i] - horsesPower[j];
            else
                currentGap = horsesPower[j] - horsesPower[i];
                
            if (currentGap < min)
                min = currentGap;
                
            if (currentGap == 1)
            {
                i = N;
                j = N;
            }
        }
    }
    // Write an action using cout. DON'T FORGET THE "<< endl"
    // To debug: cerr << "Debug messages..." << endl;

    std::cout << min << std::endl;
}

Le problème étant pour que un N très grand (100 000) le code est trop lent. Une idée pour accélérer les calculs d'écarts ?

EDIT : problème résolu 

int main()
{
    int N;
    std::cin >> N; std::cin.ignore();
    
    std::vector<int> horsesPower;
    for (int i = 0; i < N; i++) {
        int Pi;
        std::cin >> Pi; std::cin.ignore();
        
        horsesPower.push_back(Pi);
    }
    
    int min = std::numeric_limits<int>::max();
    
    std::sort(horsesPower.begin(), horsesPower.end());
    
    for (size_t i = 0; i < N - 1; ++i)
    {
        int currentGap = horsesPower[i+1] - horsesPower[i];
        if (currentGap < min)
            min = currentGap;
        if (currentGap == 1)
            break;
    }
    
    // Write an action using cout. DON'T FORGET THE "<< endl"
    // To debug: cerr << "Debug messages..." << endl;

    std::cout << min << std::endl;
}

-
Edité par Adraekor 8 juillet 2017 à 9:46:52

On le dit tout le temps, les algorithmes de la bibliothèque standard, c'est la vie

3 remarques :

Avec vector, chaque push_back peut redimensionner le tableau, ce qui est très peu performant. Tu connais la taille avant, donc dimensionné le tableau à la création puis utilisés [].

Tu peux utiliser http://en.cppreference.com/w/cpp/algorithm/adjacent_difference pour calculer la difference entre 2 elements adjacents dans le vector. (Avec une fonction lambda personnalise pour ajouter une condition d'arrêt si la difference vaut 1).

Mais tu devrais évaluer le gain de cette condition d'arrêt. Peut etre que ca n'est pas optimal, voire que ça fait perdre du temps en moyenne. (optimisation dépendante des données)

EDIT : int -> size_t dans la premiere boucle for.

-
Edité par gbdivers 8 juillet 2017 à 10:57:26

gbdivers a écrit:

Avec vector, chaque push_back peut redimensionner le tableau, ce qui est très peu performant. Tu connais la taille avant, donc dimensionné le tableau à la création puis utilisés [].

ça ne pose pas de problème qu'il y ait 100 000 cases ? Je ne connais la taille réelle qu'après le cin, donc il faudrait toujours déclarer un array 100 000 (alors que par exemple dans le premier cas j'ai un tableau de 3 cases)

gbdivers a écrit:

Tu peux utiliser http://en.cppreference.com/w/cpp/algorithm/adjacent_difference pour calculer la difference entre 2 elements adjacents dans le vector. (Avec une fonction lambda personnalise pour ajouter une condition d'arrêt si la difference vaut 1).

Mais tu devrais évaluer le gain de cette condition d'arrêt. Peut etre que ca n'est pas optimal, voire que ça fait perdre du temps en moyenne. (optimisation dépendante des données)

gbdivers a écrit:

EDIT : int -> size_t dans la premiere boucle for.

-
Edité par gbdivers il y a 20 minutes

-
Edité par Adraekor 8 juillet 2017 à 11:21:21

Adraekor a écrit:

ça ne pose pas de problème qu'il y ait 100 000 cases ? Je ne connais la taille réelle qu'après le cin, donc il faudrait toujours déclarer un array 100 000 (alors que par exemple dans le premier cas j'ai un tableau de 3 cases)

Je parle bien de vector, pas de std::array. (Ca ferait exploser la Pile d'utiliser std::array)

std::vector<int> horsesPower(N);
for (int i = 0; i < N; i++) {
    int Pi;
    std::cin >> Pi; std::cin.ignore();
         
    horsesPower[i] = Pi;
}

Adraekor a écrit:

Je ne connais pas les lambda j'irais regarder 

Les lambdas ne sont pas obligatoires, cela permettra d'ajouter ta condition d'arrêt si tu veux. Mais essaie déjà sans la condition d'arret (donc sans lambda.