Cod sursa(job #435570)

Utilizator DonPushmeMilitaru Adrian DonPushme Data 7 aprilie 2010 17:13:53
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 2.67 kb
#include <stdio.h>
#include <stdlib.h>
#include <queue>
#include <deque>
#include <vector>
#include <functional>

using namespace std;
typedef struct fruct{
        int greutate;
        int inaltime;       
}fruct;

int compare (const void * a, const void * b)  // functie de comparare folosita de qsort
{
      return (  ((fruct*)a)->inaltime - ((fruct*)b)->inaltime );
}

int main(){
    FILE* f,*g;
    
    f = fopen("gutui.in","rt");
    g = fopen("gutui.out","wt");
    
    int n,h,u;
    int height;
    int i;
    int niv_curent;
    
    fruct* v;
    v = (fruct*)malloc(100000*sizeof(fruct));
    
    fscanf(f,"%d%d%d",&n,&h,&u);
    
    for(i = 0; i < n; i++){
              fscanf(f,"%d%d\n",&height,&v[i].greutate);
              
              v[i].inaltime=(h-height)/u; // inaltimea reprezinta nivelul pe 
                                          // care se afla fructul curent.
                                          
                                          // pe nivelul 0 se afla fructele cele mai
                                          // departate de Gigel. Acestea nu pot
                                          // fi culese decat la primul pas. Fructele
                                          // de pe nivelul 1 pot fi culese in primii
                                          // 2 pasi, s.a.m.d.
                                          
    }
 
    qsort (v, n, sizeof(fruct), compare); // sortam fructele in functie de inaltime
    
    priority_queue < int, vector<int>, greater<int> > minheap;

    
    i=0;
    while(i<n){
            niv_curent=v[i].inaltime;
            while((niv_curent==v[i].inaltime)&&(i<n)){ // inseram toate fructele de pe
                                                       // nivelul curent in coada de prioritati
                       minheap.push(v[i].greutate);
                       i++;
            }
            
            while((int)minheap.size()>niv_curent+1){
                   minheap.pop(); // scoatem din coada cele mai mici elemente
                                  // astfel incat pentru pasul urmator (k) sa avem
                                  // in coada de prioritati maxim k-1 elemente
            }
            
                    
    }
    
    // la sfarsitul ciclului vom avea in coada de prioritati exact greutatile
    // fructelor ce trebuiesc culese de Gigel.
    
    unsigned int s=0;
    while((int)minheap.size()>0){         
                     s+=(int)minheap.top(); // facem suma greutatilor
                     minheap.pop();                      
    } 
    
    

    fprintf(g,"%d",s);
    fclose(f);
    fclose(g);
}