Aiuto Lotteria di Quadri 0/100

Aiuto
1 
int quadri(int N, long long M, int V[]) {
    // Scrivete qui la vostra soluzione
    int B=N/2;
    bool a=false;
    for(int i=0;i<N;i++){
       long long tot=0;
       for(int j=i;j<B+i;j++)tot+=V[j];
       if(tot>M){
          if(a){
             return B--;
          }else{
             i=0;
             B--;
          }
       }else if(i==N-2){
          i=0;
          B++;
          a=true;
       }
    }
    return B;
 }

Ho pensato ad un approccio diverso, dato che un precedente codice che avevo scritto non andava oltre il 45. Nonostante gli esempi di test in locale siano giusti, sul sito degli allenamenti il risultato è output non corretto.

2

Ciao, provando la tua soluzione in locale mi sbaglia gli esempi :thinking:

Per risolvere questo problema ci sono almeno 2 strategie:

  • ricerca binaria sulla risposta. Riesci a controllare se una lunghezza B va bene in \mathcal{O}(n)?

  • sliding window. Per ogni i, considera l’intervallo [i,j] con j massimo e somma \leq M. C’è un modo per trovare questi intervalli in \mathcal{O}(n)? Una volta che hai gli intervalli, cos’è la risposta?