Cod sursa(job #441102)

Utilizator rafaela_vRafaela Voiculescu rafaela_v Data 12 aprilie 2010 19:21:03
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 3.1 kb
// Voiculescu Rafaela 321CA

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <values.h>
#include <algorithm>
#include <vector>
using namespace std;

#define Max MAXINT

typedef struct{
    int h; //inaltimea crengii pe care se afla gutuia
    int g; //greutatea gutuii
} gutuie;

int compara(void* a,void* b)
{
    unsigned int val_a,val_b;
    val_a=(*((gutuie *)a)).h;
    val_b=(*((gutuie *)b)).h;

    if(val_a<val_b)
        return 1;
    else
        if(val_a>val_b)
            return -1;
        else
            return 0;
}

int main()
{
    //deschidere fisier de intrare, respectiv fisier de iesire
    FILE *in,*out;
    in=fopen("gutui.in","r");
    out=fopen("gutui.out","w");

    //citim numarul de gutui, inaltimea maxima si cu cat se ridica crengile
    int N,H,U;
    int i,j,ord,size,ales;
    unsigned long suma=0;
    fscanf(in,"%d%d%d",&N,&H,&U);

    //alocam spatiu
    gutuie *date;
    date=(gutuie*) calloc(N,sizeof(gutuie));

    //citim datele despre fiecare creanga
    for(i=0;i<N;i++)
    {
        fscanf(in,"%d%d",&date[i].h,&date[i].g);
        //daca deja e prea sus
        if(date[i].h>H)
        {
            i--;
            N--;
        }
    }

    //sortam descrescator dupa inaltimea la care se afla crengile
    qsort(date,N,sizeof(gutuie),(__compar_fn_t)&compara);

    vector<int> v;

    //cream un heap in care vom retine practic solutia (greutatile gutuilor alese pentru a obtine suma maxima)
    make_heap(v.begin(),v.end());
    
    for(i=0;i<N;i++)
    {
        //calculam pentru fiecare gutuie numarul sau de ordine maxim (adica dupa cate alte gutui
        //ar putea fi culeasa fara ca inaltimea crengii pe care se afla sa depaseasca valoarea H
        ord=(H-date[i].h)/U+1;
        if(ord<N)
            ales=ord;
        else
            ales=N;
        size=(int)v.size();

        //se adauga la heap atatea elemente de Max cat e diferenta intre numarul de ordine maxim al
        //gutuii si capacitatea actuala a heap-ului (in caz ca incare cea din urma e < decat prima)
        //sau cat e diferenta intre numarul total de gutui si capacitatea heap-ului (in caz ca nr de
        //ordine > N) -> pentru ca altfel ar putea fi risc de a se incerca alocarea unui vector de
        //2 milioane de elemente.
        for(j=0;j<(ales - size);j++)
        {
            v.push_back(Max);
            push_heap(v.begin(),v.end());
        }
        //scoatem valoarea maxima din heap si daca e mai mare decat Max-greutatea gutuii pentru care analizam
        //o inlocuim cu aceasta

        if(v[0]>(Max-date[i].g))
        {
            pop_heap(v.begin(),v.end());
            v.pop_back();
            v.push_back(Max-date[i].g);
            push_heap(v.begin(),v.end());
        }
    }

    //facem suma tuturor greutatilor gutuilor alese (tinand cont ca greutatea unei gutui e Max-v[i]
    //deoarece asa a fost retinuta in heap pentru a se putea scoate elementul maxim
    for(i=0;i<(int)v.size();i++)
        suma+=(Max-v[i]);
    fprintf(out,"%lu\n",suma);

    //eliberam spatiul alocat
    free(date);

    //inchidem fisierele
    fclose(in);
    fclose(out);
    
    return 0;
}