Cod sursa(job #438240)

Utilizator copotalex copot Data 10 aprilie 2010 16:35:10
Problema Gutui Scor 100
Compilator c Status done
Runda teme_upb Marime 2.14 kb
#include <stdio.h>
#include <stdlib.h>

// structuri de date folosite
// pentru reprezentarea gutuilor si a heapului binar

typedef struct {
	long h;
	long g;
} gutuie;

typedef struct {
	long *a;
	long n;
} heap;

gutuie *vg;
long N, H, U;
heap h;

void citeste()
{
	FILE *f = fopen("gutui.in", "rt");
	int i;
	if ( f == NULL )
		return;
		
	fscanf(f, "%ld%ld%ld", &N, &H, &U);
	vg = (gutuie*)calloc(sizeof(gutuie), N);
	h.a = (long*)calloc(sizeof(long), N);
	for (i = 0; i < N; i++) {
		fscanf(f, "%ld%ld", &vg[i].h, &vg[i].g);
	}
	fclose(f);
}

// intoarce pasul la care gutuia 'gut' s-ar pierde daca nu ar fi culeasa
int pas(gutuie gut)
{
	return (H - gut.h) / U + 1;
}

// functia de comparare pentru qsort
// gutuile sunt sortate crescator dupa pasul la care se pierd
int comp(const void *s1, const void *s2)
{
	return ( H - ((gutuie*)s1)->h ) / U - ( H - ((gutuie*)s2)->h ) / U;
}

// functii pentru implementarea heapului
void swap(heap *h, int i, int j)
{
	int tmp = h->a[i];
	h->a[i] = h->a[j];
	h->a[j] = tmp;
}

void addHeap(heap *h, int x)
{
	int i;
	h->n++;
	i = h->n;
	h->a[i] = x;
	
	while (i > 1 && h->a[i/2]<x) {
	  swap(h, i, i/2);
	  i = i / 2;
	}
}

inline int indmax(heap *h, int i)
{
	int st, dr, m;
	
	st = 2*i;
	dr = 2*i + 1;
	if ( st <= h->n && h->a[st] > h->a[i] )
	  m = st;
	else
	  m = i;
	if ( dr <= h->n && h->a[dr] > h->a[m])
	  m = dr;
	return m;
}

void heapify(heap *h, int i)
{
	int im;
	while (i <= h->n) {
	  im = indmax(h, i);
	  if (i == im)
		break;
	  swap(h, i, im);
	  i = im;
	}
}

int delHeap(heap *h)
{
	int hmax;
	if ( h->n < 1 )
	  return 0;
	hmax = h->a[1];
	h->a[1] = h->a[h->n];
	h->n--;
	heapify(h, 1);
  
	return hmax;
}

int main(int argc, char **argv)
{
	long sol, maxg, nci, ncmax, i;
	
	citeste();

	qsort(vg, N, sizeof(gutuie), comp); 

	ncmax = pas(vg[N-1]);

	i = N - 1;
	h.n = 0;
	sol = 0;
	for (nci = ncmax; nci >= 1 && i >= 0; nci--) {
		while ( pas(vg[i]) == nci && i >= 0) {
			addHeap(&h, vg[i].g);
			i--;
		}
		maxg = delHeap(&h);
		sol += maxg;
	}
	while ( h.n > 0 && nci >= 1 ) {
		maxg = delHeap(&h);
		sol += maxg;
		nci--;
	}

	FILE *f = fopen("gutui.out", "wt");
	fprintf(f, "%ld\n", sol);
	fclose(f);
	
	return 0;
}