#include <bits/stdc++.h>
using namespace std;
vector<int> s;
bool babbo;
int c=0, u, B=0;
int quadri(int N, long long M, int V[]) {
int i=0;
if(!babbo){
u=N;
babbo=true;
for(int x=0; x<N; x++) s[x]=V[x];
}
for(int x=0; x<u; x++) if(s[i]>M) return B;
B++;
c++;
u--;
while((c+i)<(N-1)){
s[i]+=V[c+i];
++i;
}
return quadri(N, M, V);
}
l’algoritmo crusha appena chiama la funzione, oppure quando returna dentro se stessa.
sono abbastanza sicuro di aver fatto una cosa illegalissima, solo che è il primo esercizio che faccio sulla ricerca o quello che è. Sarei molto felice se mi faceste capire l’errore in modo da capire meglio l’argomento, grazie in anticipo.
i = indice, B = soluzione, M = massimale da non superare, babbo= bool per fare le istruzioni sotto la condizione una sola volta, u= N che ogni volta diminuisce per evitare che l’algoritmo confronti un elemento, già confrontato, inutilmente, vector s = vettore parallelo su cui verrà istituita la somma per andare di coppie fino a gruppi da n, c = metodo per far partire V[i] più avanti (servirà quando la funzione ritornerà se stessa)
la prima condizione nel for in realtà sarà l’operazione fondamentale per il ritorno della funzione, essendo che solo quando sarà vera la funzione terminerà ritornando il valore B. La prima volta quel for confronterà con M i quadri singoli, e nel caso, ritornerà 0 essendo che anche vendere solo un quadro porterebbe una perdita a Fabio. Dopo il for siamo sicuri che almeno un quadro possa essere comprato senza perdite, quindi incrementiamo B, c e decrementiamo u. c incrementata servirà per eseguire correttamente la somma tra il vettore parallelo s e V: s[0] si sommerà con s[1] e così via creando nel vettore s una somma di tutte le combinazioni adiacenti possibili nel vettore V.
dopo di che ritorniamo la funzione in modo tale che si ripeta questo meccanismo ma con le coppie di quadri adiacenti, e qui servirà la decrementazione di u, per fare in modo che l’algoritmo non prenda in considerazione s[3] che vale quanto V[3].
Dopo aver controllato che anche prendendo 2 quadri adiacenti Fabio non ci perde, facciamo lo stesso procedimento per creare i gruppi da 3 quindi s[0] che conterrà (V[0] + V[1]) si sommerà con V[2] diventando così (V[0] + V[1] + V[2]) mentre s[1] sarà (V[1] + V[2] + V[3]) e così si confronteranno i gruppi da 3 quadri consecutivi.
P.S. l’ho modificato mettendo anche una condizione alla fine per il quale se B != N allora ritorna la funzione, nel caso contrario ritorna B, in modo che sia pure sicuro che se uno può comprare TUTTI i quadri senza che Fabio ci perda allora la funzione si ferma lì a forza.
incollo qui il nuovo codice:
#include <bits/stdc++.h>
using namespace std;
vector<int> s;
bool babbo;
int c=0, u, B=0, i=0;
int quadri(int N, long long M, int V[]) {
i=0;
if(!babbo){
u=N;
babbo=true;
for(int x=0; x<N; x++) s[x]=V[x];
}
for(int x=0; x<u; x++) if(s[i]>M) return B;
B++;
c++;
u--;
while((c+i)<(N-1)){
s[i]+=V[c+i];
++i;
}
if(B != N) return quadri(N, M, V);
return B;
}
non comprendo come io abbia fatto a non vedere alcuni degli errori tipo la i come indice al posto della x. Ma biasimo me stesso, essendo che sto cercando di studiare troppe cose in troppo poco tempo, e la sera in cui ho fatto il problema ero in burnout. Comunque debuggo sempre con gli esempi ma mi dava errore anche su vsc, e adesso so perchè, comunque grazie mille dell’aiuto, ti segno come soluzione ma penso che farò da capo il problema con la binary search che è l’obbiettivo dell’esercizio.
dopo ben 7 mesi, studiando di più, sono ritornato su questo problema e l’ho risolto, alla fine ho usato il two pointer method per ridurre il tempo di esecuzione praticamente sotto i 0.025s, così facendo la complessità è al massimo O(2N) quindi lineare, ossia O(N). Poi ho creato un set di long long, (anche se bastava int, ma non si è mai troppo sicuri) così facendo mi sono salvato ogni lunghezza di striscia di quadri che risultava più costosa del massimale M, e infine stampo la striscia non utilizzabile più piccola - 1, se il set non è vuoto. N se il set è vuoto ma la somma non è 0, perchè magari puoi prendere tutti i quadri e non superare il biglietto. Se non volete spoilerato nulla, ho censurato tutto apposta, ma vi do comunque un indizio, io NON ho usato la ricerca binaria, anche se è nel tag del sito, non vedo proprio come si possa usare visto che serve un vettore ordinato e noi non possiamo ordinarlo. Comunque non sto dicendo che non si possa fare con essa, ma io personalmente non l’ho usata e va più che bene come soluzione. Se non avete ancora capito, vi lascio direttamente il codice:
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int quadri(int N, ll M, int V[]){
set<ll> notsol;
ll left = 0, right = 0, sum = 0;
while(right < N){
sum += V[right++];
if(sum > M){
notsol.insert(abs(left - right));
while(left < N && sum > M) sum -= V[left++];
if(sum <= M) notsol.insert(abs(left - right) + 1);
}
}
if(!notsol.empty()) return *notsol.begin() - 1;
if(sum != 0) return N;
return 0;
}
Ciao, a cosa ti serve il set? Se non sbaglio basta tenersi il minimo (peraltro con il set la complessità è O(N\log N)).
Per quanto riguarda la binary search, ci sono almeno due modi di usarla: il primo è binsearchare la prima lunghezza k tale che esista un sottoarray lungo k con somma maggiore di M; l’altra è per ogni posizione binsearchare (con le somme prefisse) quanto ci si può espandere a destra.
ah ma sono tipo un coglione, grazie mille, studiando tutte ste cose a volte mi dimentico delle basi. Riguardo la binary search non ho capito bene, ma penso sarà il prossimo argomento da approfondire. Qui sotto il codice aggiornato:
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int quadri(int N, ll M, int V[]){
ll left = 0, right = 0, sum = 0, best = INT_MAX;
while(right < N){
sum += V[right++];
if(sum > M){
best = min(abs(left - right), best);
while(left < N && sum > M) sum -= V[left++];
if(sum <= M) best = min(abs(left - right) + 1, best);
}
}
return (best < INT_MAX) ? best - 1 : N;
}
