Premetto che è da poco che mi affaccio a problemi di questo tipo.
Perlopiù i testcase sono positivi, ma ci mette troppo tempo per alcuni.
So che esiste la shadow windows (credo si chiami cosi’), ma c’e’ un modo per risolverlo con la binary search?
Consigli?
Sotto vi lascio il codice e la spiegazione di esso:
Essenzialmente la funzione controllo verifica se è possibile sommare tutti gli elementi dei sottoarrey lunghi ‘pos’ di v, restando sotto la soglia di ‘m’, se è possibile ritorna true, altrimenti false.
Le chiamate a questa funzione avvengono da binary_search, che verifica grazie a una binary search il valore massimo con cui la funzione controllo ritorna true.
La funzione quadri non fa altro che chiamare binary_search, e verificare i casi speciali in cui la risposta dev’essere 0 o N
#include<bits/stdc++.h>
using namespace std;
bool controllo(int pos,int n,unsigned long long m, int v[]){
unsigned long long lav=0;
for(int i=0;i<=n-pos;i++){
for(int j=i;j<pos+i;j++){
lav+=v[j];
if(lav>m) return false;
}
lav=0;
}
return true;
}
int binary_search(bool r,int left,int right,int v[],long long&m,int&n){
if(left<=right){
int half=(right+left)/2;
if(controllo(half,n,m,v)) return binary_search(true,half+1,right,v,m,n);
else return binary_search(false,left,half-1,v,m,n);
}else if(r){
if(controllo(left,n,m,v))return left;
return left-1;
}else{
return right;
}
}
int quadri(int N, long long M, int V[]) {
int ans = binary_search(1,0,N,V,M,N);
if(ans==N+1) return ans-1;
else if(ans==-1) return 0;
else return ans;
}