#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);
}
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
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