Cod sursa(job #440355)

Utilizator johnbBaranga Ionut johnb Data 12 aprilie 2010 00:08:11
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 4.69 kb
#include <fstream>
#include <stdlib.h>

using namespace std;

// gutuie
struct gutuie {
	int g;      // greutatea
    int n;      // nr max de gutui culese anterior pt care gutuia ramane accesibila, numit "nivel"
};

// nod de lista inlantuita
struct nod {
	int val;    // valoarea = greutatea gutuii
	nod* next;

	nod() {
		next = NULL;
	}
};

#define S (sizeof(gutuie))


// comparara dupa nivel - criteriu primar si dupa greutate, criteriu secundar
int cmp_n(const void* fp1, const void* fp2) {
	gutuie* f1 = (gutuie*)fp1;
	gutuie* f2 = (gutuie*)fp2;
	int r = f1->n - f2->n;
	return (r == 0 ? f1->g - f2->g : r);
}




int main() {
	ifstream in ("gutui.in");
	ofstream out("gutui.out");
	int n, h, u, r = 0, nr = 0, ch, cg, cn, cnr, i, j, k;
	gutuie *gutui;
	nod** gn;	
	in >> n >> h >> u;
	gutui = new gutuie[n];


	/***********************************************************************************************************
	 * - citire din fisier 
	 * - o prima selectie - selectatrea cazurilor convenabile, adica
	 *						eliminarea gutuilor la care nu se poate ajunge din prima , adica nivelul < 0 si
	 *						a celor cu greutate nula (daca exista)
	 * - nr gutuilor ramase dupa aceasta prima selectie fiind nr <= n
	 *
	 ***********************************************************************************************************/
	
    r = 0;
	for (i = 0; i < n; i++) {
		in >> ch >> cg;          // citire inaltime si greutate
		cn = (h - ch);           // calcul nivel
		if (cn >= 0 && cg > 0) { // se adauga numai cazurile convenabile 
			r += cg;
			gutui[nr].g = cg;
			gutui[nr].n = cn / u;                                                
			nr++;
		}
    }

	n = nr; 
	if (n <= 1) {
		out << r;
		return 0;
	}
  
	qsort(gutui, n, S, cmp_n);     // sortare dupa nivel O(n log n)
	int maxn = gutui[n - 1].n + 1; // nr de niveluri
	gn = new nod*[maxn];           // vector de liste inlantuite, 
								   // qn[i] = inceputul unei liste cu gutuile de pe nivelul i, in ordinea descrescatoare a greutatii

	/**********************************************************************************************************************************
	 *
	 * initial, consider ce se aleg gutuile care sunt capete de lista (cu greutatea ce mai mare) pe fiecare nivel
	 * insa o gutuie de pe un nivel superior unui nivel i, care nu este maxima pentru acel nivel (nu este cap de lista)
	 * poate inlocui o gutuie de pe nivelul i, daca are o greutate mai mare ca aceata
	 *
	 * voi face o parcurgere crescatoare a nivelurilor, incepand cu nivelul 1, facand unde este posibil aceste inlocuiri
	 *
	 **********************************************************************************************************************************/

	for (i = 0; i < maxn; i++)
		gn[i] = NULL;

	j = 0; // nivelul curent
	for (i = 0; i < n; i++) {
		while (gutui[i].n != j) 
			j++;
		nod* nn = new nod;
		nn->val = gutui[i].g;
		nn->next = gn[j];
		gn[j] = nn;
	}

	int m, mi; bool ok;

	// pentru fiecare nivel, incepand cu 1
	for (i = 1; i < maxn; i++) {
		nod* nn = gn[i];

		// daca exista mai mult de o gutuie pe nivelul i
		if (nn == NULL || nn->next == NULL) {
			continue;
		}

		nn = nn->next;
		nr = 1;
again:
		// se gaseste gutuia cu greutatea minima "m" de nivel < i, precum si indexul acesteia, "mi"
		ok = false; 
		m = INT_MAX;
		for (j = i - 1; j >= 0; j--) {
			if (gn[j] == NULL) {
				if (m != 0) {
					m = 0;
					mi = j;
				}
			} 
			else {
				if (gn[j]->val < m) {
					m = gn[j]->val;
					mi = j;
				}
			}
		}

		// daca urmatoarea gutuie de pe nivelul i este mai grea decat minima, aceasta o va inlocui
		if (nn->val > m) {
			ok = true;
			if (m == 0)
				gn[mi] = new nod;
			gn[mi]->val = nn->val;
		}

		nr++;
		nn = nn->next;

		/******************************************************************************************************************************
		 *
		 * daca gutuia curenta a inlocuit gutuia cu greutate minima (altfel cu siguranta nici o alta gutuie de pe nivelul i 
		 *                                                           ce urmeaza in lista, avand greutatea mai mica nu o va inlocui)si
		 *      mai exitsta o gutuie pe nivelul i si
		 *      nr de gutui de pe nivelul i care au inlocuit alte gutui <= i
		 * se mai incearca o inlocuire
		 *
		 *******************************************************************************************************************************/
		if (nr <= i && nn != NULL && ok)
			goto again;
	}

	// se aduna gutuile dupa efectuarea tuturor inlocuirilor
	r = 0;
	for (i = 0; i < maxn; i++)
		r += ((gn[i] == NULL) ? 0 : gn[i]->val);
	out << r;

	return 0;
}