Lotteria di quadri 1

Aiuto
1

Volevo risolvere questo problema e ci sono riuscito sfruttando il binary search in modo ricorsivo; con qualsiasi esempio io provi, il risultato che ottengo è quello giusto e la complessità è di circa O(log2N) (ad occhio); tuttavia, sottoponendolo, molti risultati escono sbagliati compreso il primo caso esempio che ho provato ed esce corretto.

Ecco il codice

static int N;
static long long M;
static int* V;
static int B;

int SommaLotto(int i,int f){
	int somma = 0;
	for(int inizio = i; inizio < f; inizio++){
		somma += V[inizio];
		if(somma > M)
			return -1;
	}
		return somma;
}

int BinarySearch(int B = 0,int maxB = 0,int mid1 = N){
	int calc = 0;
	int mid = (B + mid1)/2;
	if(mid == B)//se il valore si ripete,siamo arrivati alla soluzione
		return mid;
	else{
	
		for(int inizio = 0; inizio < N - mid + 1; inizio++){
			calc = SommaLotto(inizio,inizio+mid);
			if(calc < 0){
				if(mid < maxB)
					return maxB;
				return BinarySearch(B*(-1),maxB,mid);
			}
		}
		if(mid > maxB)	
			return BinarySearch(mid,mid,mid1);
		else
			return BinarySearch(mid,maxB,mid1);
	}
	return mid;
}

// Declaring functions
int quadri(int N, long long M, int* V){
	int Mcopy = M;
	for(int i  = 0; i< N; i++){//per controllare se B == N
		Mcopy -= V[i];
	}
	if(Mcopy > 0)
			return N;
		else
			return BinarySearch();
}

Grazie in anticipo!! :smile:

2

Aggiungendo nella funzione quadri le inizializzazioni delle variabili statiche:
::N = N;
::V = V;
::M = M;
e dichiarando long long Mcopy le cose migliorano (35/100) ma compaiono gli “execution timed out”.
Penso che dovresti trovare una versione più efficiente della SommaLotto (somme prefisse?). che comunque dovrebbe restituire un long long.

3

Inoltre, consiglio di provare ad individuare un approccio con complessità lineare, è un’idea molto semplice (il corpo della funzione quadri è composto da solo 8 righe), nonostante un algoritmo con complessità temporale \mathcal O(NlogN) sia sufficiente.