Cod sursa(job #441505)

Utilizator Cristea_AdrianCristea Adrian Cristea_Adrian Data 12 aprilie 2010 22:42:00
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 2.33 kb
#include <stdio.h>
#include <stdlib.h>
#include <map>

using namespace std;

//Structura in care se vor pastra cate niveluri mai pot urca gutuile si masa lor
typedef struct {
        int nivel;
        int masa;
        } Gutui;

//Functia ce contine criteriul de comparare pentru qsort
//Se sorteaza dupa nivel si dupa masa in cazul in care nivelurile sunt egale
int compare(const void *c, const void *d) {
     const Gutui *a = (const Gutui *)c;
     const Gutui *b = (const Gutui *)d;
     
     if(a->nivel!=b->nivel)
                         return (a->nivel - b->nivel);
     return(b->masa - a->masa);
}

int main() {
    int h_max, nr_gutui, d_h;
    int i, j, nr_puse=0;
    Gutui *gut;
    multimap <int, int > puse;
    multimap <int, int>::iterator iter;
    int strans=0;
    
    FILE *in, *out;

    in=fopen("gutui.in","r");
    out=fopen("gutui.out","w");
    
    fscanf(in,"%d ", &nr_gutui);
    fscanf(in,"%d ", &h_max);
    fscanf(in,"%d", &d_h);
        
    gut=(Gutui *)malloc(nr_gutui*sizeof(Gutui));
    
    for(i=0;i<nr_gutui;i++) {
    //se citeste masa si inaltimea gutuilor si se calculeaza cate niveluri mai pot urca
         fscanf(in,"\n%d %d",&j, &gut[i].masa);
         gut[i].nivel=(h_max-j)/d_h+1;
         }
    //se sorteaza gutuile dupa inaltime si dupa masa
    qsort(gut, nr_gutui, sizeof(Gutui), compare);
    
    //pentru fiecare gutuie daca se poate ajunge la ea se adauga in multimap
    for(i=0;i<nr_gutui;i++) {
         if(gut[i].nivel-nr_puse>0) {
              puse.insert( pair<int, int> (gut[i].masa, 0)); 
              nr_puse++;
         }
    //daca s-a depasit nivelul la care se putea ajunge cu o unitate se verifica daca 
    //masa gutuii curente este mai mare decat cea mai mica din multiset se inlocuieste
    //aceasta cu valoarea curenta
         else 
              if(puse.size()>0)
                   if(gut[i].masa>(puse.begin())->first) {
                        puse.erase(puse.begin());
                        puse.insert( pair<int, int> ( gut[i].masa, 0));
                   }             
    }
    //se parcurge multisetul pentru a calcula masa maxima
    for(iter=puse.begin();iter!=puse.end();iter++) 
         strans+=iter->first;
    
    fprintf(out,"%d",strans);

    fclose(in);
    fclose(out);
           
    return 0;
}