Cod sursa(job #439254)

Utilizator cristinam.tanaseTanase Cristina cristinam.tanase Data 11 aprilie 2010 14:43:34
Problema Gutui Scor 80
Compilator cpp Status done
Runda teme_upb Marime 2.9 kb
  #include<stdio.h>
 // #include<conio.h>

 
         int h[100000];   //inaltime
         int g[100000];   //greutate
        
 //gutu gutui[100000];      
     int oc[100000];    // are avlori 0/1; daca prioritatea a fost data =1  
    
    void quickSortG(int vect[], int stanga, int dreapta) {  
       int i = stanga, j = dreapta;  
          int tmp1,tmp2; 
          int pivot = vect[stanga ];  
          while (i <= j) {  
                while (vect[i]> pivot)  
                      i++;  
                while (vect[j] < pivot)  
                      j--;  
               if (i <= j) {  
                     tmp1 = vect[i];
                     tmp2 = h[i];  
                     vect[i] =vect[j];
                     h[i]=h[j];  
                     vect[j] = tmp1;
                     h[j]=tmp2;  
                     i++;  
                     j--;  
               }  
          
         };  
         if (stanga < j)  
               quickSortG(vect, stanga, j);  
         if (i < dreapta)  
              quickSortG(vect, i, dreapta);  
   }   
    
   int main(){
       
    FILE *f,*f1;
    int N, H, U, i, auxh,max=0,k,s=0,stanga;
    f = fopen( "gutui.in", "r" );
    f1 = fopen( "gutui.out", "w" );
    fscanf(f, "%d", &N);
    fscanf(f, "%d", &H);
    fscanf(f, "%d", &U);
    
     for( i = 0; i < N; i ++){       
           fscanf ( f, "%d", &auxh );     //citim ialtimea
          h[i] = (H-auxh)/U+1;     // pe ce nivel se afla gutuia
          if(h[i] > max)           //nivelul maxim 
             max=h[i];               
        
          fscanf ( f, "%d", &g[i] ); //citim greutatea
     
          }

    quickSortG(g,0,N-1);          //sortam dupa greutate
  
  int ind,j;
  int cules=0;
   i=0;
  int ok=1;
   while(i<N){                      //parcurgem gutuile in ordinea greutatii,pana cand prioritatea ajunge 0
            
              if(oc[h[i]]==0 ){
                                oc[h[i]]=1;       //alocam prioritatea     
                                s=s+g[i];         //gutuia este culeasa
                                //cules++;
                                }
                                else { ind=h[i];  //vrem sa acordam prima prioritate disponibila
                                     while(oc[ind]!=0 && ind>0 )  
                                        ind--;           //prioritatea va fi mai mica decat cea gutui[i].h
                                        if(ind>0){       //daca s-a gasit o prioritate disponibila, o alocam
                                        oc[ind]=1;
                                        s=s+g[i];}  //culegem gutuia
                                        }                                
                                i++;                   
  }
  
fprintf(f1,"%d",s);        
       //  getch();
         return 0; 
     
             
    
}