Cod sursa(job #439114)

Utilizator bogdanl_yexbogdan bogdanl_yex Data 11 aprilie 2010 13:11:44
Problema Gutui Scor 0
Compilator cpp Status done
Runda teme_upb Marime 1.61 kb
#include <stdio.h>
#include <stdlib.h>
#include <queue>
using namespace std;

typedef struct GUT{
        int h;//inaltime la care se afla gutuia
        int g;  // greutatea gutuii      
}GUT;


int compare (const void * a, const void * b){//functie de comparare pe care o utilizez la sortarea dupa inaltime
  return ( *(int*)b - *(int*)a );
}



int main(){
 FILE* fisierin=fopen("gutui.in","r");
 FILE* fisierout=fopen("gutui.out","w");
 int n,h,u,i;
 GUT* vec;
 priority_queue< int, vector<int>, greater<int> > Q;
  
 fscanf(fisierin,"%d ",&n); 
 fscanf(fisierin,"%d ",&h); 
 fscanf(fisierin,"%d ",&u); 
 
 
 vec=(GUT*)malloc(n*sizeof(GUT));//vector de gutui

 for(i=0;i<n;i++){
  fscanf(fisierin,"%d",&vec[i].h);
  fscanf(fisierin,"%d",&vec[i].g);
  
}

qsort (vec, n, sizeof(GUT), compare);//sortez descrescator  dupa inaltime







Q.push(vec[0].g);
h=h-u;//se ridica celelalte gutui cu u unitati
for(i=1;i<n;i++){  //parcurg restul de gutui             
     if(vec[i].h<=h){          //verific daca mai pot culege 
       Q.push(vec[i].g);
       h=h-u;
       
}

     else{// daca in Q am o gutuie mai usoara  o inlocuiesc daca nu trec la urmatoarea
         
          if(vec[i].g > Q.top()){
           Q.pop();
           Q.push(vec[i].g);
           }
          
          }
          }
int cant_max=0;//cantiatea maxima de gutui pe care o pot culege
while(Q.empty()!=0){
 cant_max=cant_max+Q.top();//calculez cantitatea maxima de gutui
 Q.pop();
}
fprintf(fisierout,"%d \n",cant_max);
          


 fclose(fisierin);
 fclose(fisierout);
 return 0; 
   
}