Pagini recente » Cod sursa (job #480855) | Cod sursa (job #2523355) | Cod sursa (job #2385831) | Cod sursa (job #2728441) | Cod sursa (job #439943)
Cod sursa(job #439943)
#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;
}