Cod sursa(job #440527)

Utilizator adriana.erbaruAdriana Erbaru adriana.erbaru Data 12 aprilie 2010 05:42:11
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 4.33 kb
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;

struct fructa
{
    long h, g, n;
    // h = inaltimea la care se afla gutuia
    // g = greutatea gutuii
    // n = numarul maxim de gutui care pot fi culese inainte ce aceasta
    //     sa poata fi culease
    // n = [ (H - h) / U ] ( [ ] = parte intreaga)
};

fructa f[100000];

int cmpN(const void * p, const void * q) 
// functia cmpN ("compara-n") va fi apelata cu parametrii de tip fructa
// este corespunzatoare relatiei de ordine dupa care se sorteaza vectorul f[] 
// fructaA "<=" fructaB daca fructaA.n <= fructaB.n (detalii despre motivele acestei alegeri in explicatia algoritmului)
{
    fructa x = *(fructa*)p;
    fructa y = *(fructa*)q;
    return (x.n - y.n);
}

int cmpG(long p, long q) 
// functia cmpG ("compara-g") va fi apelata cu parametrii de tip long
// compara fructele ce au drept indici parametrii dati, dupa greutate
// sta la baza realizarii structurii de heap in vectorul sol
// cmpG(p, q) intoarce "1" daca f[p] este mai greu decat f[q], si "0" in caz contrar
// prin urmare, vectorul sol va fi un min-heap raportat la greutatea fructelor
{
    fructa x = f[p];
    fructa y = f[q];
    if (x.g > y.g )
    {
        return 1;
    }
    else
    {
        return 0;
    }

}

int main()
{
    long nSol=0, H, N, U; 
    // nSol = numarul de elemente din solutia curenta
    // H, N, U sunt conform enuntului
    long gSol=0, i, k;
    // gSol = greutatea solutiei curente 
    // altfel spus, suma greutatilor gutuilor din solutia curenta
    
    vector<long> sol;
    vector<long>::iterator it;
    
    // sol = solutia curenta; in sol se retin indicii (din f[]) ai fructelor
    
    FILE *fin, *fout;
    fin = fopen("gutui.in", "r");
    fout = fopen("gutui.out", "w");   
    fscanf(fin, "%li%li%li", &N, &H, &U);
    // scanf("%li%li%li", &N, &H, &U);
       
    for(i=0;i<N;i++)
    {
        fscanf(fin, "%li%li", &f[i].h, &f[i].g);
        // scanf("%li%li", &f[i].h, &f[i].g);
        f[i].n = (H-f[i].h) / U;
    }
        
    qsort(f, N, sizeof(fructa), cmpN);
    // se sorteaza vectorul de fructe dupa n (definit in structura fructa)
    
    // se parcurce vectorul de fructe incepand de la 0    
    for(k=0;k<N;k++)
    {
        // se compara n-ul fructei f[k] cu numarul de elemente din solutia curenta
        // nSol = numarul de elemente din sol (solutia curenta)
        if(f[k].n >= nSol) // daca f[k].n >= nSol , inseamna ca putem adauga fructa f[k] la solutia curenta
        {
            sol.push_back(k); // adaugam indicele k in vectorul sol
            push_heap( sol.begin(), sol.end(), cmpG ); // refacem structura de heap a vectorului sol
            
            nSol++; // incrementam nSol (deoarece am adaugat un element in solutie)
            gSol += f[k].g; // actualizam greutatea solutiei (adaugand greutatea fructei f[k])
        }
        else // daca f[k].n < nSol , atunci conform explicatiilor algoritmului, f[k].n = nSol - 1
             // in acest caz, cautam elementul cu greutatea minima din solutie si vedem daca trebuie sa il 
             // inlocuim cu f[k] sau nu (in functie de care are greutatea mai mare)
            if (f[sol.front()].g < f[k].g) 
            // daca greutatea lui f[k] este mai mare decat greutatea "minimului" din solutie, atunci
            // il vom elimina pe acest minim din solutie si il vom adauga pe f[k] 
            {
                // datorita structurii de heap a lui sol, f[sol.front()] este elementul cu greutatea minima din solutie
                gSol = gSol + f[k].g - f[sol.front()].g; // actualizam greutatea solutiei
                
                pop_heap( sol.begin(), sol.end(), cmpG ); 
                // pregatim eliminarea "minimului" punand indicele acestuia la coada lui sol
                sol.pop_back();
                // eliminam din sol indicele elementului minim
                
                sol.push_back(k); 
                // adaugam incidele k in vectorul sol 
                push_heap( sol.begin(), sol.end(), cmpG );
                // refacem structura de heap a vectorului sol
            }
    }                  
      
    fprintf(fout, "%li", gSol);
    // printf("%li", gSol); // afisarea solutiei
    
    fclose(fin);
    fclose(fout);
    return 0;
}