Cod sursa(job #440017)

Utilizator marina.lecuLecu Marina marina.lecu Data 11 aprilie 2010 21:26:50
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 2.68 kb
//Lecu Marina 322CB
// TEMA 1 - Problema 2

#include <stdio.h>
#include <stdlib.h>
//#include<conio.h>
#include <algorithm>
using namespace std;
#include <map>
using namespace std;
#include <vector>
using namespace std;

typedef struct
{
    unsigned int h,g;
} TGutuie;

bool compg(const TGutuie &g1,const TGutuie &g2)
{
    return g1.g < g2.g;
}

bool comph(const TGutuie &g1,const TGutuie &g2)
{
    return g1.h > g2.h;
}

bool compg2(const unsigned int &g1,const unsigned int &g2)
{
    return g1 > g2;
}
int main()
{
    unsigned int N,H,U,G=0,i,nculese=0;
    FILE *in,*out;
    TGutuie* gutui;
    vector<unsigned int> culese;
    vector<unsigned int>::iterator it;

    in=fopen("gutui.in","r");
    out=fopen("gutui.out","w");
    
    fscanf(in,"%u %u %u",&N,&H,&U);                 //citire N,H,U                
    gutui = (TGutuie*) malloc(N*sizeof(TGutuie));   //alocare vector gutui
    //citire inaltimi si greutati gutui
    for(i=0; i<N; i++)
        {
            fscanf(in,"%u %u",&(gutui[i].h),(&gutui[i].g));
            if(gutui[i].h > H)
            {
                i--;
                N--;
                continue;
            }            
            gutui[i].h = H - U *((H-gutui[i].h)/U);
            //niv.nmax = (H - gutui[i].h)/U +1;
        }
        
    sort(gutui,gutui+N,comph);                   //sortare in ordine descrescatoare dupa inaltime
    make_heap(culese.begin(),culese.end(),compg2);
    for(i=0; i < N; i++)
    {
        //printf("h:%u   g:%u\n",gutui[i].h,gutui[i].g);
        if(nculese < (H - gutui[i].h)/U +1)    //daca mai putem culege de pe nivelul curent
        {
            culese.push_back(gutui[i].g);
            push_heap(culese.begin(),culese.end(),compg2);   //inseram in heap
            nculese++;                          // crestem nr de gutui culese
        }
        else                                    // nu mai putem culege decat daca renuntam la una anterioara
        {
            if(*(culese.begin()) < gutui[i].g)
            {
                pop_heap(culese.begin(),culese.end(),compg2);
                culese.pop_back();
                culese.push_back(gutui[i].g);
                push_heap(culese.begin(),culese.end(),compg2);
            }
        }
/*        printf("heap: ");
        for(it=culese.begin(); it!=culese.end(); it++)
        {
            printf("%u ",*it);
        }
        printf("\n"); 
*/
    }
    
    //calcul suma greutati
    for(it=culese.begin(); it!=culese.end(); it++)
    {
        G+= *it;
    }
//    printf("G: %u",G);
//    getch();
    fprintf(out,"%u",G);    
    fclose(in);
    fclose(out);    
    return 0;
}