Cod sursa(job #438822)

Utilizator prik_mihMihai Prica prik_mih Data 11 aprilie 2010 01:10:33
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 3.97 kb
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#include <functional>
//#include <conio.h>
using namespace std;
unsigned int n,h,u;
//structura pentru retinerea datelor de intrare
typedef struct {
        unsigned int height;
        unsigned int weight;
        unsigned int clas;                                                      //variabila care imi indica pasul maxim la care
        }gutuie;                                                                //poate fi culeasa o gutuie                                                            
//gutuie *vect;
//functie care compara doua gutui dupa greutate
bool my_compare(const gutuie &a,const gutuie &b){
    //gutuie *unu=(gutuie *) a;
    //gutuie *doi=(gutuie *) b;
    return (a.weight > b.weight);
    
}

int main(){
    int i,j,max_dif=0,k=0,nrgutui=0,sum=0;
    int *solutie;
    FILE *fin=fopen("gutui.in","r");
    FILE *fout=fopen("gutui.out","w");
    fscanf(fin,"%d",&n);
    fgetc(fin);
    fscanf(fin,"%d",&h);
    fgetc(fin);
    fscanf(fin,"%d",&u);
   
    //respect restrictile
    if(n<1||n>100000) 
         return 1;
    std::vector<gutuie> vect;
    gutuie aux;     
    //citesc datele de intrare
    for(i=0;i<n;i++){
       fgetc(fin);
       fscanf(fin,"%d",&aux.height);
       //verific daca gutuia poate fi culeasa
       if(aux.height<=h){
                       fgetc(fin);
                       fscanf(fin,"%d",&aux.weight);
                       aux.clas=(h-aux.height)/u+1;
                       if(aux.clas>max_dif)                                 //vad cate gutui pot culege maxim
                                max_dif=aux.clas;
                                }
        else {
            i--;
            n--;
            }
        vect.push_back(aux);
   }
   //vector care are pe pozitia i greutatea gutui care a fost culeasa la pasul i
   //initializat cu 0
   solutie=(int *)calloc(max_dif+1,sizeof(int));
   //sortez dupa greutate
   
      
   std::sort(vect.begin(),vect.end(),my_compare);
   //qsort(vect,n,sizeof(gutuie),my_compare);
  
    //incep sa culeg gutui cat mai grele pana am cules destule
    for(i=0;i<n && nrgutui<=max_dif;i++){
              k=vect[i].clas;
              if(solutie[k]==0){                                                //nu am mai cules gutuie la pasul k
                   solutie[k]=vect[i].weight;
                   nrgutui++;
                   }
              else 
                 for(j=k-1;j>=0;j--)                                            //am cules gutuie la pasul k si incerc 
                    if(solutie[j]==0){                                          //sa culeg gutuia curenta anterior          
                        solutie[j]=vect[i].weight;
                        nrgutui++;
                        break;
                    }
   }                 
                                  
                                           
                   /*
   metoda pe care am abordat-o prima data
   dar care era prea lenta datorita qsortului de mai jos
   in teorie si ea functioneaza
   
      while(i<n){
                  k=vect[i].clas;
                  for( g=depl ; g < k && i < n; g++)
                      solutie[depl++]=vect[i++].weight;
                  schimb=0;
                   qsort(solutie,depl,sizeof(int),comp);
                              
                 for(g=i;vect[g].clas==k&&schimb<k;g++)
                     for(j=0;j<depl&&schimb<k;j++)
                          if(solutie[j]<vect[g].weight) {
                                 solutie[j]=vect[g].weight;
                                 schimb++;
                                 break; 
                          }
                  i=g;
         
       }
       
                 */            
  //calculez greutatea maxima     
      for(i=1;i<=max_dif;i++)
          sum+=solutie[i];
         
      fprintf(fout,"%d",sum);
     // getch();
      return 0;
}