#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