Cod sursa(job #439691)

Utilizator alexqawsFasui Alexandru alexqaws Data 11 aprilie 2010 18:23:50
Problema Gutui Scor 10
Compilator cpp Status done
Runda teme_upb Marime 5.64 kb
#include <iostream>
#include <fstream>
//#include <stdlib.h>
#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 */
unsigned int n; /* numarul de gutui */
gs *gt; /* vectorul de gutui */
//unsigned int *luate;
//unsigned int *niv /* cate mai pot lua de pe niv. respectiv */;
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 */
unsigned int nivmin = UINT_MAX; /* nivelul minim */


/* functia de comparare pentru qsort 
    sortam gutuile in ordine descrescatoare a greutatii, iar in caz de egalitate, 
    pe cea care se afla la o inaltime (nivel) mai mare */

int comp(const unsigned int a, const unsigned int b){
    return b - a;
}

priority_queue<unsigned int, std::vector<unsigned int>, std::greater<unsigned int> > q;
    
int compare (const void * a, const void * b) 
{
    if( ((gs *)b)->ng != ((gs *)a)->ng ){
        if ( ((gs *)b)->ng < ((gs *)a)->ng ){
            return 1;
        }
        else{
            return -1;
        }
    }
    else{
        if( ((gs *)b)->gg > ((gs *)a)->gg ){
            return 1;
        }
        else
            if ( ((gs *)b)->gg < ((gs *)a)->gg ){
                return -1;
            }
            else{
                return 0;
            }
    }
}

/* determina greutatea maxima ce poate fi culeasa,
incercam sa luam primele p gutui ca greutate, in masura in care se poate;
stim ca pentru fiecare pas ar trebui sa luam cea mai grea gutuie din cele ramase, deoarece
numarul de gutui ce poate fi cules este fix, si intotdeauna este de preferat sa luam o gutuie
mai grea decat una mai usoara; deasemenea, pentru a putea lua gutuia de la apsul curent,
trebuie sa verificam in primul rand dacase mai pot lua gutui de pe acest nivel, si daca
dupa ce luam aceasta gutuie mai putem lua si gutuile mai grele decat ea, de pe nivelele inferioare */
int get_gmax(){
    unsigned int i, j, k, t, y, flag, br;

    //cout<<endl<<endl;

    /* se iau primele p gutui, de la cea mai grea la cea mai usoara */
    for( i = 0; i < n; i++ ){
        
        //cout<<nr_luate<<endl;
        
        if( gt[i].ng > nr_luate){
            q.push ( gt[i].gg );
            gmax = gmax + gt[i].gg;
            if(nr_luate < p){
                nr_luate ++;
            }
            //cout<<"pus: "<<gt[i].ng<<"   "<<gt[i].gg<<endl;
        }
        else{
            //cout<<"d"<<endl;
            //cout<<"top: "<<q.top()<< "   "<<gt[i].ng<<"   "<<gt[i].gg<<endl;
            if(gt[i].gg > q.top()){
                gmax = gmax - q.top();
                q.pop();
                //cout<<"x"<<endl;
                q.push ( gt[i].gg );
                gmax = gmax + gt[i].gg;
                if(nr_luate < p){
                    nr_luate ++;
                }
            }
        }
        

    }
    
    
    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 */
        
        if( gt[i].ng < nivmin ){ /* determinam nivelul minim */
            nivmin = gt[i].ng;
        }
        
    }  
    
    /* numarul de gutui ce se pot lua se calculeaza in functie de numarul de nivele accesibile */
    p = nivmax - nivmin + 1;
    
    if(p > n){ /* daca exista mai putine gutui decat nivele, se pot lua maxim n gutui */
        p = n;
    }
    
    //cout<<p<<endl;
    
    //luate = (unsigned int *)malloc( p * sizeof( unsigned int ));
    //niv = (unsigned int *)malloc( p * sizeof( unsigned int ));
    
    qsort (gt, n, sizeof(gs), compare); /* sortam gutuile descrescator in functie de greutate */
    
    //for(i=0;i<n;i++){
        //cout<<gt[i].ng<<"   "<<gt[i].gg<<endl;
    //}
    
    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();
    
    //cin.get();//to_comment
        
    return 0;
}