Pagini recente » Cod sursa (job #160205) | Cod sursa (job #683865) | Cod sursa (job #2927536) | Cod sursa (job #2509336) | Cod sursa (job #433913)
Cod sursa(job #433913)
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
typedef struct obiecte {
long inaltime;
long greutate;
long round;
} Obiecte;
int comparator (const void *O1, const void *O2)
{
Obiecte *o1, *o2;
o1 = (Obiecte *)O1;
o2 = (Obiecte *)O2;
if (o1->round < o2->round)
return -1;
if (o1->round == o2->round) {
if (o1->greutate < o2->greutate)
return 1;
else
if (o1->greutate == o2->greutate)
return 0;
else
return -1;
}
return 1;
}
int compHeap (void *a, void *b)
{
Obiecte *o1, *o2;
o1 = (Obiecte *)a;
o2 = (Obiecte *)b;
if (o1->greutate < o2->greutate)
return -1;
else
if (o1->greutate == o2->greutate)
return 0;
return 1;
}
int main()
{
FILE *f = fopen("gutui.in", "r");
FILE *g = fopen("gutui.out", "w");
long N, H, U, G = 0, i, *obj;
Obiecte *gutui;
/* Numărul de gutui */
fscanf(f, "%ld", &N);
gutui = (Obiecte *)calloc(N, sizeof(Obiecte));
obj = (long *)calloc(N + 1, sizeof(long));
/* Înălțimea maximă la care poate ajunge Gigel */
fscanf(f, "%ld", &H);
/* Cu cât se ridică crengile */
fscanf(f, "%ld", &U);
for (i = 0; i < N; i++) {
fscanf(f, "%ld", &gutui[i].inaltime);
fscanf(f, "%ld", &gutui[i].greutate);
gutui[i].round = (H - gutui[i].inaltime) / U + 1;
}
qsort(gutui, N, sizeof(Obiecte), comparator);
long k = 0;
vector<Obiecte *> heap;
vector<Obiecte *>::iterator it;
// make_heap(heap.begin(), heap.end(), compHeap);
for (i = 0; i < N; i++) {
if (k < gutui[i].round) {
k++;
G += gutui[i].greutate;
gutui[i].round = k;
heap.push_back(&gutui[i]);
push_heap(heap.begin(), heap.end(), compHeap);
// insertHeap(&heap, &gutui[i], compHeap);
}
else {
/* caut în heap un element cu greutate mai mică */
Obiecte *gutuie;
// gutuie = (Obiecte *)elem_atHeap(heap, 0); /* greutatea minimă din heap */
gutuie = (Obiecte *)heap.front();
if (gutuie && gutuie->greutate < gutui[i].greutate) {
gutui[i].round = gutuie->round;
G -= gutuie->greutate;
g += gutui[i].greutate;
pop_heap(heap.begin(), heap.end(), compHeap);
heap.pop_back();
heap.push_back(&gutui[i]);
push_heap(heap.begin(), heap.end(), compHeap);
// gutuie = extrageHeap (&heap, compHeap);
// insertHeap(&heap, &gutui[i], compHeap);
}
}
}
fprintf(g, "%ld", G);
return 0;
}