Cod sursa(job #438155)

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

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

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

typedef struct {
  int a[100000];
  int n;
} heap;

gutuie vg[100000];
unsigned 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);
	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;
	}
}

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;
}