Cod sursa(job #437535)

Utilizator arrowedgeDragos Dinu arrowedge Data 9 aprilie 2010 21:00:50
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 5.08 kb
#include <stdlib.h>
#include <stdio.h>

typedef struct {
        int w;
        int h;
        int t;
        }gutuie;
        

typedef struct {
        int *cont;
        int dim;
        }maxheap ;

void insert ( maxheap * h, int x){//functia de inserare (clasica) pentru maxheap reprezentat ca vector
     int poz =++h->dim;
     for( ; poz > 1 && x > h->cont[ poz / 2 ]; poz/= 2) 
                h->cont[poz] = h->cont[poz/2];
     h->cont[poz] = x;
    
     }
      
int compare (const void * elem1, const void * elem2){
     gutuie * e1=(gutuie *)elem1;
     gutuie * e2=(gutuie *)elem2;
    return (-e1->t + e2->t);
}
      
      
void swap (maxheap & h, int i, int j){
            int t;
            t=h.cont[i];
            h.cont[i]=h.cont[j];
            h.cont[j]=t;
            }
            
           
      
      


void heapify (maxheap& h, int i) {
           int st, dr,m;
           int aux;
           st=2*i;
           dr=st+1;
           if (st<=h.dim && h.cont[st]>h.cont[i])
              m=st;
           else m=i;
           if (dr<=h.dim && h.cont[dr]>h.cont[m])
              m=dr;
           if (m!=i){
           swap (h,i,m);
           heapify(h,m);
           }
           
       }


  
  int del (maxheap & h) {
      int hmax;
      if (h.dim<=0) return -1;
      hmax= h.cont[1];
      h.cont[1]=h.cont[h.dim];
      h.dim --;
      heapify (h,1);
      return hmax;
      }
      
      
         
     

int main(){
    int N,H,U;
    FILE * f=fopen("gutui.in","r");
    fscanf(f,"%d %d %d\n", &N,&H,&U);
    
    gutuie gutui[N];//vectori cu greutatile si inaltimile gutuilor
    
    int i,j;
    for (i=0;i<N;i++)
     fscanf(f, "%d %d\n", &(gutui[i].h),&(gutui[i].w));
     
     
     //calculam pentru fiecare gutuie, momentul de timp maxim (t) la care se poate culege 
     
     for (i=0;i<N;i++) {
      if (gutui[i].h<=H) gutui[i].t=(H-gutui[i].h)/U+1;
      else (gutui[i].t=-1);
      }
      
      
      //algoritmul alege gutuia cea mai grea care se poate alege la fiecare moment de timp, incepand cu cel mai indepartat
      
      //calculam maximul din vectorul t (sa stim cate momente de timp consideram)
      int max=gutui[0].t;
      for (i=1;i<N;i++) if (gutui[i].t>max) max =gutui[i].t;
      
     /* maxheap *heap=(maxheap *)malloc((max+1)*sizeof(maxheap));// un vector de heapuri (pentru fiecare moment de timp), primul element al heapului corespunzator 
                      //va contine gutuia cu greutate maxima (am folosit maxheap pentru a mari viteza aflarii celui mai mare element
      
      for (j=0;j<max;j++){
          heap[j].dim=0;//initializam heapul
          heap[j].cont=(int *)malloc(N*sizeof(int));
          }*/
     for (i=0;i<N;i++) printf("%d ", gutui[i].w);
     qsort ( (void *)gutui,N, sizeof(gutuie), compare );


       
     /* for (i=0;i<N;i++){//pentru fiecare gutuie                                 
        if (t[i]>=1)  mylist[t[i]-1].insert(it[t[i]-1],w[i]);//adaugam greutatea gutuii in heapul corespunzator momentului de timp t[i] 
          }*/
       
        int aux=0;//calculam cate heap-uri sunt vide  
        int cant=0;//cantitatea de fructe culeasa
        
        maxheap choices;//heapul in care tinem solutiile posibile (gutuile ce pot fi alese) la feicare pas
        choices.dim=0;//initializam heapul
          choices.cont=(int *)malloc(N*sizeof(int));
      //   for (i=0;i<N;i++) printf("%d ", gutui[i].t);
      //   printf(" %d ", max);
         j=0;
      for (i=max;i>0;i--){
      //  if (heap[i].dim>=1) cant=cant+heap[i].cont[1];// se culege gutuia si se adauga greutatea ei
        //  for (j=1;j<=(int)mylist[i].size();j++) {//restul de gutui pot fi alese si la pasul anterior ..
            
            while (gutui[j].t==i) {
              insert (&choices,gutui[j].w);//le inseram in heapul corespunzator pasului anterior
              
          //    printf("%d ", gutui[j].w);
              j++;
              }
          if (choices.dim>=1) {cant+=choices.cont[1]; 
                              del(choices);
                              }   
              
          }
        //  cant=cant+choices.cont[1];
          
 /* //     for (j=1;j<=heap[0].dim;j++) printf("%d ", heap[0].cont[j]);   
  //     printf("\n");
      for (j=1;j<=aux+1;j++){ //pentru cate alegeri mai avem (aux +1)
        //alegem din primul heap (corespunzator celui mai apropiat moment de timp)
         cant=cant+heap[0].cont[1];
         del(heap[0]);
     //   for (j=1;j<=heap[0].dim;j++) printf("%d ", heap[0].cont[j]);
    //    printf("\n");
         }*/
       //   printf("%d ",cant);
       //   getchar();
          FILE * g=fopen("gutui.out", "w");
          fprintf(g,"%d",cant);
          fclose(g);
          
          }
          
          
          
      
      
   //if (heap[poz].dim==alloc[poz]) {heap[poz].cont=(int *)realloc(heap[poz].cont,alloc[poz]+10);
                                              //alloc[poz]+=10;
                                               //}