Cod sursa(job #463700)

Utilizator simona.poilincaSimona Poilinca simona.poilinca Data 17 iunie 2010 12:02:18
Problema Gutui Scor 100
Compilator c Status done
Runda teme_upb Marime 3.16 kb
#include <stdio.h>
#include <stdlib.h>

typedef struct {
	unsigned int height;
	unsigned int weight;
	} gut;

void print (gut *g,unsigned int n)
{
	unsigned int i;
	for (i=0; i<n; i++)
		fprintf (stdout, "%d-------%d\n", g[i].height, g[i].weight);
	fprintf (stdout, "\n");
}

void print_heap (unsigned int *heap, unsigned int size)
{
	unsigned int i;
	for (i=0; i<size; i++)
		fprintf (stdout, "%d ", heap[i]);
	fprintf (stdout, "\n");
}

/* Functie comparator folosita pentru qsort */
int cmp (const void *a, const void *b)
{
	return (*(gut*)a).height - (*(gut*)b).height;
}

void swap (unsigned int* a ,unsigned  int* b )
{
	unsigned int aux;
	aux = *a;
	*a = *b;
	*b = aux;
}

unsigned int left (unsigned int i)
{
	return i*2+1;
}

unsigned int right (unsigned int i)
{
	return i*2 + 2;
}

unsigned int parent (unsigned int i)
{
	return (i-1)/2;
}

/* Functie care urca un element in heap */
void up (unsigned int *heap, unsigned int poz)
{
	if (parent(poz) < 0 || poz == 0)
		return;
	if (heap[parent(poz)] < heap[poz])
	{
		swap (&heap[parent(poz)], &heap[poz]);
		poz = parent(poz);
		up (heap, poz);
	}
}

/* Functie care insereaza un element in heap */
void heap_put (unsigned int *heap, unsigned int cost, unsigned int size)
{
	heap[size] = cost;
	up (heap, size);	
}

/* Functie care coboara un element in heap */
void down (unsigned int *heap, unsigned int poz, unsigned int size)
{
	unsigned int crt;
	
	if ( (left(poz) < size ) && ( heap[left(poz)] > heap[poz] ) )
		crt = left(poz);
	else
		crt = poz;

	if  ( (right(poz) < size ) && ( heap[right(poz)] > heap[crt] ) )
		crt = right(poz);	

	if ( crt != poz ) 
	{
		swap ( &heap[crt] , &heap[poz] );
		down ( heap , crt , size );
	}
}

/* Functie care returneaza maximul din heap */
unsigned int heap_get (unsigned int *heap, unsigned int size)
{
	if (size == 0)
		return 0;
	unsigned int toret = heap[0];
	heap[0] = heap[size-1];
	down (heap, 0, size - 1);
	return toret;
}	

int main()
{
	FILE *fin, *fout;
	unsigned int n, u, h, max, size, aux, i, niv;
	gut *gutui;
	unsigned int *heap;
	
	fin = fopen ("gutui.in", "r");
	fout = fopen ("gutui.out", "w");
	
	fscanf (fin, "%d %d %d\n", &n, &h, &u);
	if (n<1 || n>100000)
		return 1;
	gutui = (gut*)malloc(n*sizeof(gut));
	heap = (unsigned int*)calloc(n, sizeof(unsigned int));
	
	for (i=0; i<n; i++)
		fscanf (fin, "%d %d\n", &(gutui[i].height), &(gutui[i].weight));
		
	/* Sortare in ordine crescatoare dupa inaltimile gutuilor */
	qsort (gutui, n, sizeof(gut), cmp);
	
	max = 0;
	niv = (h -gutui[0].height)/u + 1;
	size = 0;
	for (i=0; i<n; i++)
	{
		/* Daca s-a depasit inaltimea maxima */
		if (gutui[i].height > h)
			break;
		aux = (h - gutui[i].height)/u + 1;
		/* Daca s-a efectuat un salt de nivel */
		if (niv!=aux)
		{
			/* Cat timp mai pot sa scot gutui din heap */
			while (niv > aux)
			{
				if (size > 0)
				{
					max += heap_get (heap, size);
					size--;
				}
				niv--;
			}
		}
		heap_put (heap, gutui[i].weight, size);
		size++;
	}
	
	/* Scoaterea gutuilor care au dreptul de a fi culese din heap */
	while (niv>0 && size>0)
	{
		max += heap_get (heap, size);
		size--;
		niv--;
	}
	
	fprintf (fout, "%d\n", max);
	
	fclose (fin);
	fclose (fout);
	free (heap);
	free (gutui);
	return 0;
}