Aiuto per garage

Ciao a tutti, ho provato a fare garage, problema apparentemente semplice, con questo algoritmo:


inizialmente, mi tengo due contatori: available, che indica il numero di posti disponibili, e minimum, che indica il minimo posto disponibile, inizializzati rispettivamente a N e 0.
quando entra una macchina, se available == 0 la metto nella coda, altrimenti la posiziono nella posizione minimum, e calcolo il costo da aggiungere alla somma, e in aggiunta ovviamente diminuisco il valore di available
quando invece una macchina esce, se la coda è vuota faccio diventare minimum il numero del parcheggio appena liberato (se è inferiore a minimum stesso) e aumento il valore di available, se invece ha qualche elemento posiziono la macchina in testa alla coda nel posto liberato, e calcolo il prezzo da aggiungere.

Nonostante non riesca a trovare errori nel programma, ricevo un punteggio di 33.33/100.
Qualcuno sa aiutarmi?

Ma va in TLE o WA?

da errore nell’output, nessun errore ne di memoria ne di tempo… e i testcase funzionano

Quando togli la macchina dalla coda per metterla nel parcheggio decrementi available? Non l’hai scritto… Se non è questo il problema, posta il codice.


EDIT: Ops scusa non avevo visto che incrementavi available solo se la coda è vuota :slight_smile:
in >> N >> M;
	available = N;
	for(int n = 0; n < N; n++)
	{
		in >> parks[n].cost;
		parks[n].available = true;
	}
	for(int n = 1; n <= M; n++)
	{
		in >> cars[n].peso;
		cars[n].park = -1;
	}
	int x;
	int sum = 0;
	for(int n = 0; n < 2*M; n++)
	{
		in >> x;
		if(x < 0)
		{
			cout << "Car " << abs(x) << " is about to leave!" << endl;
			if(!carQueue.empty())
			{
				Car a = carQueue.front();
				carQueue.pop();
				cout << "Car with weight " << a.peso << " comes to " << cars[abs(x)].park << endl;
				a.park = cars[abs(x)].park;
				sum += a.peso * parks[a.park].cost;
			}
			else
			{
				minimum = min(minimum, cars[abs(x)].park);
				parks[cars[abs(x)].park].available = true;
				cout << "Nobody in the queue" << endl;
				available++;
			}
			cars[abs(x)].park = -1;
		}
		else
		{
				cout << "Car " << abs(x) << " is about to enter!" << endl;
			if(available == 0)
			{
				cout << "Putting in the queue" << endl;
				carQueue.push(cars[x]);
			}
			else
			{
				while(minimum < N && !parks[minimum].available)
					minimum++;
				cout << "Car " << x << " comes to " << minimum << endl;
				cars[x].park = minimum;
				parks[minimum].available = false;
				sum += cars[x].peso * parks[minimum].cost;
				available--;
			}
		}
	}
	out << sum;
while(minimum < N && !parks[minimum].available)
minimum++;
DonaDev

Considera che in alcuni test case la seguente asserzione, posta dopo le due righe indicate sopra, fallisce.

assert(parks[minimum].available);

grazie mille :slight_smile: chiedo troppo se ti chiedo l’input del caso?

Per esempio, fallisce con questo input (output previsto 20163827):

http://d.pr/f/TlBN

Credo che il problema nasca dal fatto che quando liberi un posto per metterci l’auto A (quella in cima alla coda) effettivamente non ti salvi che l’auto A viene parcheggiata lì, lo fai nella variabile A ma non nell’array delle auto.


Quindi quando dovrai liberare il parcheggio di quell’auto (nel caso della coda vuota) eseguendo il codice
parks[cars[-x].park].available = true;
non sai che valore abbia cars[-x].park, perché non te lo sei salvato!

E’ un po’ contorto ma dovrebbe essere così

EDIT: confermo, ho fatto una leggera modifica al programma per risolvere la tua “svista” e totalizza 100/100 :slight_smile:

oddio hai ragione! cavolo i soliti errori di distrazione D: grazie infinite!