Do not gather 60 punti

#include <stdio.h>
#include <assert.h>

#define MAXN 100000

int n, d, i, j, co = 0;
int A[MAXN];

int main() {

    assert(2 == scanf("%d %d", &n, &d));
    for(i=0;i<n;i++)
        {
            assert(1 == scanf("%d", &A[i]));
        }



        for(i=n-1;i>=0;i--)
        {
            for(j=i-1;j>=0;j--)
            {
                if(A[i]-A[j]>=d)
                {
                    i--;
                    j = i-1;
                }
                if(A[i]-A[j]<d)
                {
                    co++;
                }


            }


        }

printf("%d", co);

}
1 Mi Piace

La tua soluzione ha complessitĂ  temporale O(N^2), per rimanere nel limite di tempo devi abbassarla a O(NlogN) oppure O(N).

Si lo so che devo portare i tempi sotto O n^2 ma non riesco a risparmiare tempo nel caso in cui tutti i casi sono sbagliati e quindi ti devi confrontare tutti gli elementi

Ti consiglio di dare un’occhiata a questo thread.

Ciao scusa ma credo di non aver capito la soluzione che mi hai proposto, come posso fare per cambiare il tempo di esecuzione da quadratico a lineare? Il problema è che la mia soluzione riesce a risparmiare tempo solo quando ci sono dei casi in cui la differenza tra due numeri è maggiore o uguale a d

Il ragionamento è spiegato in quel post, posso provare a fare un esempio per chiarire. Se tu hai N persone devi trovare per ogni i < N l’indice j che sarebbe l’indice della persona più a destra di i tale che risultano essere troppo vicini. Quindi se con i=3 trovi j=5 allora sai che ci sono j-i = 5-3=2 coppie per i = 3 che non vanno vene (3,4), (3,5), ripetendo il ragionamento per ogni i e sommando i risultati trovati trovi la risposta a questo problema.

Per farlo velocemente supponi che all’iterazione precedente i valeva 35 e avevi trovato j = 70, ora incrementando i a 36 sai che il nuovo j deve valere almeno 70 perché se la persona in posizione 70 era troppo vicino a quella in posizione 35 allora sarà sicuramente troppo vicina anche a quella in posizione 36. Quindi per trovare il nuovo j inizi a controllare partendo dalla posizione 70. Facendo in questo modo hai gli indici i e j che vengono entrambi incrementati N volte durante tutta l’esecuzione e quindi hai che la complessità finale è lineare