Cod sursa(job #463553)

Utilizator simona.poilincaSimona Poilinca simona.poilinca Data 16 iunie 2010 13:50:37
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 2.16 kb
#include <stdio.h>
#include <algorithm>
#include <vector>

using namespace std;

// structura gutuilor - inaltime si greutate
typedef struct quince_fruit {
	int height;
	int weight;
} qfruit;


int h, u;

// calcul nivel fata de inaltimea maxima h
unsigned int get_level (int height) {
	return (h - height)/u;
}

// functia de comparatie dupa nivelul si greutatea gutuilor
bool compare_quinces (qfruit q1, qfruit q2) {
	if (get_level(q1.height) == get_level(q2.height))
		return (q1.weight > q2.weight);
	return (get_level(q1.height) < get_level(q2.height));
}

// functia de comparatie dupa greutate 
bool min_heap_compare (qfruit q1, qfruit q2) {
	return (q1.weight > q2.weight);
}


int main() {
	FILE *in, *out;
	in = fopen ("gutui.in", "r");
	out = fopen ("gutui.out", "w");

	int n;
	qfruit *data;

	// citire date de intrare
	fscanf (in, "%d %d %d", &n, &h, &u);
	data = (qfruit *) calloc (n, sizeof(qfruit));
	for (int i=0; i<n; i++) {
		fscanf(in, "%d %d", &(data[i].height), &(data[i].weight));
	}

	vector<qfruit> fruit (data, data+n);
	vector<qfruit>::iterator it;	
	// sortare dupa nivel si greutate
	sort (fruit.begin(), fruit.end(), compare_quinces);
		
	vector<qfruit> fruitheap;
	vector<qfruit>::iterator it2;	
	it = fruit.begin();
	
	// parcurgem vectorul de gutui cu iteratorul it	
	while (it != fruit.end()) {
		
		unsigned int l = get_level ((*it).height) +1 ;
		unsigned int added = 0;
		// pentru fiecare nivel
		while (get_level ((*it).height) +1 == l && it!=fruit.end()) {
			// adaugam numarul maxim de gutui disponibile pentru acel nivel in fruitheap
			if (added < l) {
				fruitheap.push_back (*it);
				// pastram ordinea de min-heap
				push_heap (fruitheap.begin(), fruitheap.end(), min_heap_compare);
				added ++;
			}
			it ++;

		}
		// scoatem gutuile care sunt in plus pentru nivelul pe care ne aflam
		while (fruitheap.size() > l) {
			pop_heap (fruitheap.begin(), fruitheap.end(), min_heap_compare);
			fruitheap.pop_back();
		}	
	}

	// calculam suma greutatilor obtinuta
	unsigned int sum =0;
	for (it=fruitheap.begin(); it!=fruitheap.end(); it++) {
		sum += (*it).weight;			
	}	

	// afisare rezultat
	fprintf (out, "%u", sum);
	fclose (in); fclose (out);
	return 0;
}