Cod sursa(job #463386)

Utilizator simona.poilincaSimona Poilinca simona.poilinca Data 15 iunie 2010 16:43:48
Problema Gutui Scor 100
Compilator c Status done
Runda teme_upb Marime 2.62 kb
// Popescu Maria, 324CA
#include <stdio.h>
#include <stdlib.h>

typedef struct { int h, c; } Gutuie;

int n, H, U;
Gutuie G[100021]; //G[i] este gutuia i data prin inaltime si greutate
int timp[100021]; //timp[i] este numarul maxim de gutui care pot fi culese inainte
int raspuns = 0; //raspuns este raspunsul final
int *heap, heap_sz; //structura de maxim-heap

//voi sorta gutuile crescator dupa inaltime
int cmp(const void *a, const void *b)
{
	return ((Gutuie *)a)->h - ((Gutuie *)b)->h;
}

//citesc datele
void citeste()
{
	int i;

	FILE *f = fopen("gutui.in", "r");

	fscanf(f, "%d %d %d", &n, &H, &U);
	for (i = 1; i <= n; i++)
		fscanf(f, "%d %d", &G[i].h, &G[i].c);

	fclose(f);
}

//functie de interschimbare a doua elemente
void schimba(int *a, int *b)
{
	int aux = *a;
	*a = *b;
	*b = aux;
}

//urc in heap o valoare inspre radacina
void urca(int *heap, int poz)
{
	while (poz > 1)
	{
		if (heap[poz/2] < heap[poz])
		{
			schimba(heap+(poz/2), heap+poz);
			poz /= 2;
		}
		else
			break;
	}
}

//interschimb un nod cu fiul maxim pana cand nodul ajunge mai mare decat ambii fii
void coboara(int *heap, int heap_size, int poz)
{
	while (poz * 2 <= heap_size)
	{
		int mn = poz * 2;
		if (poz * 2 + 1 <= heap_size && heap[poz * 2] < heap[poz * 2 + 1])
			mn = poz * 2 + 1;
		if (heap[mn] > heap[poz])
		{
			schimba(heap+mn, heap+poz);
			poz = mn;
		}
		else
			break;
	}
}

//inserez o valoare in heap
void insereaza_in_heap(int *heap, int *heap_size, int val)
{
	(*heap_size)++;
	heap[*heap_size] = val;
	urca(heap, *heap_size);
}

//sterg maximul(radacina) si returnez acest maxim
int afla_max_si_sterge(int *heap, int *heap_size)
{
	if (heap_size == 0)
		return 0;

	int max = heap[1];
	heap[1] = heap[*heap_size];
	heap[*heap_size] = 0;
	(*heap_size)--;
	coboara(heap, *heap_size, 1);

	return max;
}

void rezolva()
{
	//sortez gutuile crescator dupa inaltime
	qsort(G+1, n, sizeof(Gutuie), cmp);

	int i, j, t, max_gutui;
	for (i = 1; i <= n; i++)
		timp[i] = (H-G[i].h)/U + 1;
	heap = (int *)malloc(sizeof(int) * (n+1));
	heap_sz = 0;

	for (i = 1; i <= n; i++)
	{
		//daca nu mai pot culege gutuia, termin
		if (G[i].h > H)
			break;

		j = i; t = timp[i];
		while (timp[j] == t)
		{
			//inserez gutuia in heap si trec la urmatoarea
			insereaza_in_heap(heap, &heap_sz, G[j].c);
			++j;
		}

		//cate gutui am timp sa culeg
		max_gutui = timp[i]-timp[j];
		while (max_gutui > 0 && heap_sz > 0)
		{
			raspuns += afla_max_si_sterge(heap, &heap_sz);
			--max_gutui;
		}

		i = j-1;
	}
}

//afisez raspunsul
void scrie()
{
	FILE *f = fopen("gutui.out", "w");

	fprintf(f, "%d\n", raspuns);

	fclose(f);
}

int main()
{
	citeste();
	rezolva();
	scrie();

	return 0;
}