Cod sursa(job #441282)

Utilizator alex.mireaAlex Mirea alex.mirea Data 12 aprilie 2010 20:53:55
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 2.72 kb

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
// h - inaltimea gutuiei
// g - greutatea gutuiei
// disp - disponibilitatea gutuiei
struct Gutuie{
	long int h,g,disp;
};

int comparaGutui(Gutuie g1,Gutuie g2){
	return g1.disp < g2.disp;
}

int main(){
	FILE *fin,*fout;
	long int n,h,u,i,gMax=0,dispCurenta;
	vector<long int> greutatiDisp;
	
	//CITIRE DATE DE INTRATRE
	fin = fopen("gutui.in","rw");
	fscanf(fin,"%ld %ld %ld",&n,&h,&u);
	vector<Gutuie> gutui(n);
	
	for (i=0;i<n;i++){
		fscanf(fin,"%ld %ld",&(gutui[i].h),&(gutui[i].g));
		gutui[i].disp = (h-gutui[i].h)/u; //stabilire life-span
	}
	
	//SORTARE - conform specificatiilor sort din 
	sort(gutui.begin(),gutui.end(),comparaGutui);
	 
	/*
	 * Disponibilitatea unei gutui = numarul de ridicari cu U a gutuiei fara a ajunge la o inaltime inaccesibila (>H)
	 *
	 * Avand gutuile aranjate dupa disponibilitate incepem rezolvarea decizand ce gutuie alegem in ordine inversa. 
	 * Alegem prima data ultima gutuie pe care o vom culege, a doua oara penultima etc.
	 *
	 * Stocam greutatile gutuilor cu aceeasi disponibilitate intr-un vector greutatiDisp pe care il aranjam ca un max-heap
	 * Astfel primul element va fi intotdeauna cel mai mare - folosirea max-heapului ne ajuta sa avem o complexitate
	 * mai mica deoarece plasarea unui element in heap se realizeaza in O(log n) unde n este adancimea heapului
	 *
	 * Din acest vector (gutui Disp) scoatem dupa trecerea la un nou nivel si actualizarea vectorului maximul, pe care il adaugam la gMax
	 * Maximul nu trebuie neaparat sa fie de la elementele cu disponibilitatea curenta ci poate fi din elementele cu disponibilitate anterioara
	 *
	 */


	dispCurenta = gutui[n-1].disp; //ultimul element din vector va avea disponibilitatea cel mai mare
	while ((gutui.size() or greutatiDisp.size()) and dispCurenta != -1){

		//actualizare vector (heap) de gutui disponibile prin adaugarea gutuilor cu aceeasi disponibilitate	
		while (gutui.size() and gutui.back().disp == dispCurenta) {
		   	greutatiDisp.push_back(gutui.back().g);
        	push_heap(greutatiDisp.begin(), greutatiDisp.end()); // refac ordinea de heap
        	gutui.pop_back();   //scot elementul din lista
    	}

		dispCurenta --;

		// adaugare cea mai mare greutate disponibila 
		if (greutatiDisp.size()){
			gMax += greutatiDisp.front();
			pop_heap(greutatiDisp.begin(),greutatiDisp.end()); // rearanjeaza heapul - cea mai mare greutate este ultima
			greutatiDisp.pop_back(); // scot greutatea
		}
		
	}

	// SCRIERE GREUTATE MAXIMA IN FISIERUL DE IESIRE
	fout = fopen("gutui.out","wt");	
	fprintf(fout,"%ld",gMax);

	//INCHIDERE FISIERE
	fclose(fin);
	fclose(fout);
	
	return 0;
}