Cod sursa(job #441608)

Utilizator TzibuTibuleac Andrei Sergiu Tzibu Data 12 aprilie 2010 23:35:32
Problema Gutui Scor 50
Compilator cpp Status done
Runda teme_upb Marime 3.07 kb
#include <stdio.h>
#include <stdlib.h>

typedef struct
{
 unsigned int niv,kg;
}GUTUIE;

int comp(const void *a,const void *b) //functia de comparare, sorteaza descrescator dupa inaltime
{                                     //daca doua gutui au aceeasi inaltime, sunt sortate descrescator dupa greutate
 unsigned int h1=((GUTUIE*)a)->niv;
 unsigned int h2=((GUTUIE*)b)->niv;
 if(h1==h2)
 {
   unsigned int kg1=((GUTUIE*)a)->kg;
   unsigned int kg2=((GUTUIE*)a)->kg;
   return kg2-kg1;  
 }
 return h2-h1;
}

void updateIns(unsigned int heap[],int index) //functia de actualizare a heap-ului dupa inserarea unui element
{
 int root=(index-1)/2;
 if(heap[root]>heap[index])
 {
   unsigned int aux;
   aux=heap[root];
   heap[root]=heap[index];
   heap[index]=aux;
   updateIns(heap,root);
 } 
}

void hIns(unsigned int heap[],unsigned int *dim,int val) //inserare la capatul heap-ului, si actualizarea sa
{
  heap[(*dim)]=val;
  updateIns(heap,(*dim));
  (*dim)++;  
}

void updateRem(unsigned int heap[],unsigned int dim,unsigned int root) //functia de actualizare a heap-ului dupa stergerea unui element
{
  unsigned int lNode=root*2+1,rNode=root*2+2,minNode=root; 
  if(lNode<dim&&heap[lNode]<heap[minNode])
    minNode=lNode;
  if(lNode<dim&&heap[rNode]<heap[minNode])
    minNode=rNode;   
  if(minNode!=root)
  {
    unsigned int aux=heap[minNode];
    heap[minNode]=heap[root];
    heap[root]=aux;
    updateRem(heap,dim,minNode);
  } 
}

void hRem(unsigned int heap[],unsigned int *dim) //stergere din varful heap-ului si actualizarea sa
{
  (*dim)--;
  heap[0]=heap[(*dim)];
  updateRem(heap,*dim,0);
}

int main()
{
  freopen("gutui.in","r",stdin);
  freopen("gutui.out","w",stdout);  
  
  unsigned int i,dim=0,sol=0,N,N2=0,H,U,niv,kg,heap[100000];
  GUTUIE vgutui[100000];
  
  scanf("%d %d %d",&N,&H,&U);
  //H/=U;
  for(i=0;i<N;i++)
  {
    scanf("%d %d",&niv,&kg);
    if(niv<=H) {vgutui[N2].niv=niv;vgutui[N2].kg=kg;N2++;}//daca gutuia citita este la o inaltime
                                                   //mai mare decat H, nu mai este introdusa in vector
  }
  N=N2;
  qsort(vgutui,N,sizeof(GUTUIE),comp);  //sortare vector gutui
    
  hIns(heap,&dim,vgutui[0].kg); //inserarea primului element din vector in radacina heap-ului
  H-=U;  
  
  for(i=1;(i<N)&&(H>=0);i++)
    if(vgutui[i].niv>H)         //daca gutuia curenta este la o inaltime mai mare decat inaltimea maxima curenta
    {                           //si daca greutatea acesteia este mai mare decat ce este in radacina heap-ului,
      if(vgutui[i].kg>heap[0])  //se sterge ce este in radacina heap-ului si se introduce greutatea gutuii curente
      {
        hRem(heap,&dim);
        hIns(heap,&dim,vgutui[i].kg);
      }
    }
    else                        //altfel se introduce greutatea gutuii curente, si se scade inaltimea maxima cu U
    {      
      hIns(heap,&dim,vgutui[i].kg);
      H-=U;
      //H--;
    }
  for(i=0;i<dim;i++)   //rezultatul va fi suma elementelor din heap
    sol+=heap[i];
  printf("%d",sol);
  return 0;
}