Ciao a tutti, ho bisogno di aiuto per risolvere il problema Lotteria di quadri.
output corretti ma molti vanno in time limit exceed, come posso ottimizzare il codice
20/100
Ecco il mio codice: #include #include
using namespace std;
int quadri(int N, long long M, int l) {
vectorV(N);
for(int i=0;i<N;i++) {
V[i]=l[i];
}
int B=N;
long long sum=0;
for(int j=0;j<N;j++) {
for(int i=0;i<=j;i++) {
sum=accumulate(V.begin()+i,V.end()-j+i,0);
if(sum>M) {
B–;
break;
}
}
}
return B;
}
Ciao, questo problema l’ho risolto un po’ di tempo fa e quindi proverò ad aiutarti e se non capisci qualcosa prova ad approfondire su internet.
Come hai notato il tuo codice fa TLE, questo è dovuto alla sua complessità temporale che se non erro è O(N^3): te hai implementato due cicli for annidati (complessità di O(N^2) con al suo interno std::accumulate (O(N)) → O(N ^ 2) * O(N) = O(N ^ 3).
Una complessità cubica con N che può arrivare a 200 000 non è fattibile (se provi a fare 200 000 ^ 3 fa 8.000.000.000.000.000, un numero di operazioni troppo grande: tieni conto che il limite di tempo è 0.3 secondi e in un secondo si eseguono circa 10^8 operazioni…).
Questa tecnica permette la risoluzione in tempo lineare (O(N)) di molti problemi che richiedono di trovare il massimo / minimo subarray che rispetti determinate condizioni.
Dopo aver risolto quadri puoi allenarti ancora su questa tecnica sul problema Training - Christmas Lights (olinfo.it), che è molto simile.
P.s. per incollare del codice usa l’opzione “testo preformattato” (il simbolo </> )
non riesco lo stesso ho provato a fare la sliding windows come mi hai detto tu e fatto anche un altro controllo, come posso risolvere?
#include <numeric>
#include <vector>
using namespace std;
int quadri(int N, long long M, int l[]) {
vector<int>V(N);
for(int i=0;i<N;i++) {
V[i]=l[i];
}
int B=N;
int temp=0;
long long sum=0;
int a=0,b=0;
for(int j=0;j<N;j++) {
temp=0;
sum=accumulate(V.begin(),V.begin()+B,0);
for(int i=0;i<=j;i++) {
if(sum>M) {
B--;
break;
}
sum-=V[i];
sum+=V[i+B];
temp++;
}
if(temp==j+1)return B;
}
return B;
};
Ciao, scrivo non per il problema lotteria di quadri ma piuttosto per chiedere aiuto riguardo a come poter scrivere messaggi: è da mezzora che cerco di capire come fare ma non trovo il modo (sono solo riuscito a rispondere a messaggi già esistenti come sto facendo ora), non è che qualcuno potrebbe dirmi come posso fare? grazie mille
Ok, se intendi creare nuovi post per chiedere informazioni, farsi aiutare o condividere qualcosa su un problema, devi solo andare nella homepage del forum e clicchi l’opzione “crea nuovo argomento” e, dopo aver selezionato le varie info del post (se è un aiuto oppure chiarimento o una segnalazione…) scrivi quello che devi scrivere e aspetti per delle risposte…
Spero tu abbia capito
