Cod sursa(job #441305)

Utilizator Emy21Filipescu Emilian Emy21 Data 12 aprilie 2010 21:05:08
Problema Gutui Scor 10
Compilator c Status done
Runda teme_upb Marime 2.51 kb
#include <stdlib.h>
#include <stdio.h>
#define CHILD(node) ((node) * 2 + 1)

typedef struct gutuie{
  int interval;
  int g;
}gutuie;

//pentru transformarea priority_queue in minheap
/*class mycomparison{
  public:
  bool operator() (const int& a, const int& b) const{
    return (a > b);
  } 
};*/

//pentru qsort
int sortare(const void * x,const void * y){
  gutuie *temp1=(gutuie*)x;
  gutuie *temp2=(gutuie*)y;
  return ( temp1->interval - temp2->interval );
};

static void heapify( int a[], int i, int n ){
	while ( CHILD( i ) < n ) {
 		int child = CHILD( i );
 		if ( child + 1 < n && a[child] > a[child + 1] )
 			++child;
  		if ( a[i] > a[child] ) {
			int temp = a[i];
			a[i] = a[child];
			a[child] = temp;
      			}
  		++i;
      	}
 }

void make_heap( int a[], int n ){
	int i = n / 2;
	while ( i-- > 0 )
		heapify( a, i, n );
}
void pop_heap( int heap[], int n ){
	int temp = heap[0];
	heap[0] = heap[n];
	heap[n] = temp;
	heapify( heap, 0, n-1 );
}
int main( void ){
	int heap[110000];
int dim=0;
	/*
	for ( i = 0; i < 11; i++ )
		heap[i] = rand() % 100;
	make_heap( heap, 11 );
	for ( n = 10; n >= 0; n-- ) {
		printf( "%d ", heap[0] );
		pop_heap( heap, n );
	}*/
int n,h,u;
  int inaltime;
  int i,rang,max = 0;
  gutuie v[110000];
  FILE *in=fopen("gutui.in","rt");
  FILE *out=fopen("gutui.out","wt");
  fscanf(in,"%d %d %d",&n,&h,&u);
  
  //priority_queue<int,vector<int>,mycomparison> minheap;
 
  for (i = 0;i < n;i++){
    fscanf(in,"%d %d",&inaltime,&v[i].g);
    v[i].interval = (h - inaltime) / u;
  }
  for (i = 0;i < n;i++)
    if (v[i].interval >= 0) 
      v[i].interval++;
  
  qsort(v,n,sizeof(gutuie),sortare);
     int j;
  i=0;
  //pozitionare pe prima gutuie disponibila (interval pozitiv)
  while(v[i].interval < 0) 
    i++;
  
  rang = v[i].interval;
  
  while (i < n){
    if (v[i].interval == rang){
        dim++;
	heap[dim-1]=v[i].g;
	make_heap(heap,dim);
      i++;
for (j=0;j<dim;j++)
    printf("p=%d ",heap[j]);
printf("\n");

printf("dim=%d g=%d\n",dim,v[i].g);
    }
      else {
	while(dim > rang) {
printf("pop=%d\n",heap[0]);

	  pop_heap(heap,dim);

	  dim--;
for (j=0;j<dim;j++)
    printf("h=%d ",heap[j]);
printf("\n");

	  }
	  
	rang=v[i].interval;
      }
for (j=0;j<dim;j++)
    printf("%d ",heap[j]);
printf("\n");
  }
  
  while(dim > rang) {
	  pop_heap(heap,dim);
		dim--;
	}
  
  for (j=0;j<dim;j++){
    max = max + heap[j];
  }
  
  fprintf(out,"%d",max);

return 0;
}