Buonasera. Ho scritto il seguente codice c++ per risolvere Lotteria di quadri (algobadge, sezione greedy) e gran parte dei testcase mi da’ output errato, anche se gli esempi mi risultano corretti. Il codice qui sotto presenta l’implementazione di una sliding window. Il punteggio uscente è 0/100. Qualcuno gentilmente potrebbe aiutarmi?
int quadri(int N, long long M, int V[]){
int B=0, it;
long long temp=-1, temp2;
for(int i=0; i<N; i++){
it=i;
temp2=0;
while(it<N&&temp2+V[it]<M){
temp2+=V[it];
it++;
}
if(temp2>temp){
temp=temp2;
B=it-i;
}
}
return B;
}
credo che il problema sia che tu stai considerando separatamente gli intervalli. ad esempio se il primo intervallo che trovi è lungo 4, e poi ne trovi uno lungo 5 con un valore temp2 più alto, tu tieni quello da 5, ma da quel che mi ricordo tu dovresti trovare una lunghezza massima che vada bene a partire da qualsiasi indice. quindi non dovresti aggiornare B in base al valore dei quadri, ma in base alla lunghezza dell’intervallo
Ciao, grazie innanzitutto di aver risposto.
Ho provato a seguire il tuo consiglio (avevo fatto un errore di comprensione del testo, grazie per avermelo fatto notare) modificando il codice tentando di trovare il valore minimo che andasse bene per qualunque posizione il blocco iniziasse. Anche con questi miglioramenti, però, ottengo testcase errati. Ci sono degli edge case che mi sono perso?
Il codice in questione:
#include<climits>
int quadri(int N, long long M, int V[]){
int B=INT_MAX, it;
long long temp=0;
bool endReached=false;
for(int i=0; i<N&&!endReached; i++){
it=i;
temp=0;
while(it<N&&temp+V[it]<M){
temp+=V[it];
it++;
}
if(it==N){
endReached=true;
}
if(it-i<B){
B=it-i;
}
}
return B;
}