Cod sursa(job #439915)

Utilizator alexqawsFasui Alexandru alexqaws Data 11 aprilie 2010 20:28:03
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 3.89 kb
#include <iostream>
#include <stdlib.h>
#include <fstream>
#include <queue>

using namespace std;

typedef struct gs{ /* structura unei gutui */
    unsigned int ng; /* nivel gutuie - in functie de h si u se pot determina anumite nivele, astfel incat
                        dupa ce a fost culeasa o gutuie vor disparea toate gutuile de pe cel mai inalt nivel curent */
    unsigned int gg; /* greutate gutuie */
} gs;

unsigned int h,u; /* h = inaltimea maxima, u = cu cat se ridica crengile dupa ce a fost culeasa o gutuie */
unsigned int n; /* numarul de gutui */
gs *gt; /* vectorul de gutui */

unsigned int nr_luate = 0;
unsigned int p; /* numarul de gutui care se pot lua; daca este posibil am dori sa luam primele p gutui ca greutate */

unsigned int gmax = 0; /* greutatea maxima */
unsigned int nivmax = 0; /* nivelul maxim */

/* coada de prioritati ce va contine greutatile gutuilor luate, in ordine crescatoare */
priority_queue<unsigned int, std::vector<unsigned int>, std::greater<unsigned int> > q;

/* functia de comparare pentru qsort 
    sortam gutuile in ordine crescatoare a nivelului pe care se afla */   
int compare (const void * a, const void * b) 
{
    if ( ((gs *)b)->ng < ((gs *)a)->ng ){
        return 1;
    }
    if ( ((gs *)b)->ng > ((gs *)a)->ng ){
        return -1;
    }
    return 0;
}

/* functia care determina greutatea maxima ce poate fi culeasa */
int get_gmax(){
    unsigned int i;

    /* se parcurg toate gutuile */
    for( i = 0; i < n; i++ ){
        
        if( gt[i].ng > nr_luate ){ /* daca gutuia curenta se poate lua atunci o culegem */
            q.push ( gt[i].gg ); /* se adauga la gutuile culese */
            gmax = gmax + gt[i].gg;
            nr_luate ++;
        }
        else{
            /* daca gutuia curenta are o greutate mai mare decat cea mai usoara gutuie culeasa
            atunci interschimbam cele doua gutui */
            if(gt[i].gg > q.top()){ 
                gmax = gmax - q.top(); /* renuntam la gutuia cu greutate minima */
                q.pop();
                q.push ( gt[i].gg ); /* adaugam noua gutuie */
                gmax = gmax + gt[i].gg;
            }
        }
        

    }
    
    return 0;
}

/* citeste datele initiale */
int read_vec(){
    ifstream fin;
    unsigned int i;
    unsigned int hg, o; /* hg = inaltime gutuie, o = offset al inaltimii */
    /* adaugam acest offset pentru ca am dori ca inaltimea maxima sa fie de forma ( const * u - 1 ),
    pentru a putea separa in mod corect nivelele, asadar trebuie sa modificam toate inaltimile in mod 
    corespunzator, adunand acest offset; astfel nivelul pentru o gutuie aflata la inaltimea hg va fi
    egal cu ( hg / u ) */
    
    fin.open("gutui.in",ios::in);
    
    fin >> n;
    fin >> h;
    fin >> u;
    
    o = u - ( h % u ) - 1; /* calculam offsetul pentru inaltime */
    
    h = h + o; /* inaltimea maxima */
    
    gt = (gs *)malloc( n * sizeof( gs )); /* vectorul de gutui */ 
    
    nivmax = h / u; /* nivelul maxim */

    for( i = 0; i < n; i++ ){
        fin >> hg;
        
        fin >> gt[i].gg;
        
        if( hg > h ){ /* daca gutuia nu este accesibila nici macar la primul pas, o ignoram */
            i--;
            n--;
            continue;
        }
        
        hg = hg + o; /* inaltimea gutuii */

        gt[i].ng = nivmax + 1 - ( hg / u ); /* nivelul gutuii => dupa cati pasi mai poate fi culeasa o gutuie */
        
    }  
    
    qsort (gt, n, sizeof(gs), compare); /* sortam gutuile crescator in functie de nivel */
    
    fin.close();
    return 0;
}

/* scrie solutia */
int write_sol(){
    ofstream fout;
    fout.open("gutui.out",ios::out);
    
    fout << gmax;
    
    fout.close();
    return 0;
}

int main(){
     
    read_vec();  
    
    get_gmax();
    
    write_sol();
        
    return 0;
}