Cod sursa(job #439112)

Utilizator vladnegaNegacevschi Vladimir-Alexandru vladnega Data 11 aprilie 2010 13:09:53
Problema Gutui Scor 50
Compilator cpp Status done
Runda teme_upb Marime 3.13 kb
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>

using namespace std;

typedef struct {
	unsigned int greutate;
	unsigned int inaltime;
} gutuie;

bool comp1(gutuie g1, gutuie g2){
	return (g1.inaltime > g2.inaltime);
}

bool comp2(gutuie g1, gutuie g2){
	return (g1.greutate > g2.greutate);
}

void rezultat(vector<gutuie> g, FILE *f){
	vector<gutuie>::iterator it;
	unsigned long long int total = 0;
	for(it = g.begin(); it != g.end(); it++)
		total += it->greutate;
	fprintf(f, "%lld", total);
}

int main(){
	FILE *in = fopen("gutui.in", "r");
	FILE *out = fopen("gutui.out", "w");
	unsigned int n,h,u,i;

	fscanf(in, "%d %d %d", &n, &h, &u);

	unsigned int ch = h;	
	vector<gutuie> gut, cos;
	vector<gutuie>::iterator it;
	vector<gutuie>::iterator it2;	
	gutuie g;
	char *aux = (char*) malloc (100 * sizeof(char));
	fgets(aux, 100, in);	// sar peste linia curenta
	
	for(i = 0; i < n; i++){
		fscanf(in, "%d %d", &g.inaltime, &g.greutate);
		gut.push_back(g);
		fgets(aux, 100, in);	//sar peste linia curenta
	}
	
	// sortez descrescator vectorul de gutui dupa inaltime
	sort(gut.begin(), gut.end(), comp1);
	
	for(it = gut.begin(); it != gut.end(); it++){
		if(it->inaltime <= h){		// daca pot ajunge la gutuie
			cos.push_back(*it);	// atunci o adaug in cos
		// in loc sa adaug U cm la inaltimea fiecarei gutui in parte de 
		// fiecare data cand culeg o gutuie, voi scadea U cm din inaltimea
		// maxima la care pot ajunge (h)
			if(h - u < 0)	// conditie pusa din cauza ca h si u sunt
				h = 0;	// unsigned int
			else
				h -= u;	// inaltimea maxima la care pot ajunge 
					// scade cu U cm
		}
		else
			break;
	}
	
	// daca am reusit sa culeg toate gutuile atunci afisez greutatea cosului
	if(gut.size() == cos.size()){
		rezultat(cos, out);
		return 0;
	}
	
	// fac un minheap al cosului ordonat dupa greutati
	make_heap(cos.begin(), cos.end(), comp2);
	
	//h = ch;		// TODO pentru varianta lui Vali asta trebuie decomentat
	
	// acum analizez gutuile care n-au intrat in cos	
	for(it2 = it; it2 != gut.end(); it2++){
		// daca greutatea gutuii analizate este mai mare decat greutatea
		// celei mai usoare gutui din cos --SI-- daca nu pot ajunge la 
		// gutuia analizata, dar ea este cu cel mult u cm mai sus decat 
		// pot ajunge eu atunci...
		if(it2->greutate > cos.front().greutate && it2->inaltime > h  && it2->inaltime <= (h + u)){
			// pun in locul celei mai usoare gutui din cos pe gutuia
			// analizata si actualizez minheap-ul
			pop_heap(cos.begin(), cos.end(), comp2);
			cos.pop_back();
			cos.push_back(*it2);
			push_heap(cos.begin(), cos.end(), comp2);
			/*cos.front() = *it2;
			sort_heap(cos.begin(), cos.end(), comp2);*/
		}
		//daca pot ajunge la gutuie atunci...
		else if(it2->inaltime <= h || it2->inaltime > h+u){
			// adaug gutuia analizata in cos
			cos.push_back(*it2);
			push_heap(cos.begin(), cos.end(), comp2);
			if(h - u < 0)							//TODO
				h = 0;							//TODO
			else								//TODO
				h -= u;	// inaltimea la care pot ajunge scade  		//TODO
					// cu u
		}
		
	}
	
	// scriu in fisierul de iesire greutatea cosului
	rezultat(cos, out);
	
	free(aux);
	fclose(in);
	fclose(out);
	
	return 0;
}