Cod sursa(job #433913)

Utilizator LieserlLaura Vasilescu Lieserl Data 4 aprilie 2010 17:49:51
Problema Gutui Scor 10
Compilator cpp Status done
Runda teme_upb Marime 2.86 kb
#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;
}