Cod sursa(job #437518)

Utilizator stefansStefan-Gabriel Sicleru stefans Data 9 aprilie 2010 20:38:18
Problema Gutui Scor 100
Compilator c Status done
Runda teme_upb Marime 4.67 kb
/*
	SICLERU STEFAN-GABRIEL
	325CA
*/

/*
N - numar de gutui din copac
H - inaltimea maxima la care ajunge Gigel
U - cu cat se ridica crengile dupa ridicarea unei gutui
*/

#include<stdio.h>
#include<stdlib.h>
#define MAX 100000

struct pair 
{
	int inaltime;
	int greutate;
};

void merge(struct pair *vector, int start, int middle, int end)
{
	int i,j;
	int n = middle - start + 1;
	int m = end - middle;
	struct pair *left = (struct pair *)calloc(n, sizeof(struct pair)); //parcurs cu i
	struct pair *right  = (struct pair *)calloc(m, sizeof(struct pair)); //parcurs cu j
	//copiez elementele
	for (i = 0; i < n; i++)
		left[i] = vector[start + i];
	for (i = 0; i < m; i++)
		right[i] = vector[middle + 1 + i];
	i = 0; 
	j = 0;
	int k = start;
	while (i < n && j < m)
	{
		if (left[i].inaltime < right[j].inaltime)
			vector[k++] = left[i++];
		else 
			vector[k++] = right[j++];	
	}
	while (i < n)
		vector[k++] = left[i++];
	while (j < m)
		vector[k++] = right[j++];
	free(left);
	free(right);
}

//functie de sortare a gutuilor dupa inaltime, in ordine crescatoare
void mergeSort(struct pair *vector, int start, int end)
{
	int middle;
	if (start < end)
	{
		middle = (start + end)/2;
		mergeSort(vector, start, middle);
		mergeSort(vector, middle + 1, end);
		merge(vector, start, middle, end);
	}
}

//implementare heap-uri(MIN-HEAP)

int heap[MAX], dimHeap=0;

int min2(int a, int b)
{ return ((a<b) ? a : b); }

int min3(int a, int b, int c)
{ return min2(min2(a,b), c); }

void swap(int *a, int i, int j)
{ int aux = a[i]; a[i]=a[j]; a[j]=aux; }

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

//descendent stang
int DS(int i)
{ return 2*i+1; }

//descendent drept
int DD(int i)
{ return 2*i+2; }

void coboaraValoare(int *heap, int poz) 
{
    for (;;)
    {
        int valMin=heap[poz], pozitieDescendent;
        if (DD(poz) < dimHeap)
        	valMin = min2(valMin, heap[DD(poz)]);
        if (DS(poz) <dimHeap)
        	valMin = min2(valMin, heap[DS(poz)]);
        if (valMin == heap[poz])
        	return; // Nu e nimic de facut aici
        else 
        	if (valMin == heap[DS(poz)])
            	pozitieDescendent = DS(poz);
        	else
            	pozitieDescendent = DD(poz);
        swap(heap, poz, pozitieDescendent);
        poz = pozitieDescendent;
    }
}

void urcaValoare(int *heap ,int poz) 
{
    // Cat timp parintele exista si are o valoare mai mare decat nodul curent...
    while (poz > 0 && heap[poz] < heap[parinte(poz)]) 
    {
         // ... interschimbam nodul curent cu parintele
        swap(heap, poz, parinte(poz));
        // Urcam pozitia curenta mai sus cu un nivel si reluam
        poz = parinte(poz);
    }
}

int minim(int *heap)
{
    // Primul element din vector este cel mai mic, conform proprietatii de heap.
    return heap[0];
}

int extrageMinim(int *heap) 
{
    // Retinem valoarea minima, o returnam la sfarsit
    int min = heap[0];
    // Inlocuim valoarea minima cu ultimul element din heap
    swap(heap, 0, dimHeap-1);
    // Scadem dimensiunea heap-ului
    dimHeap--;
    coboaraValoare(heap, 0);
    return min;
}

void adaugaValoare(int *heap, int val) 
{
    // Marim dimensiunea heap-ului
    dimHeap++;
    // Noul element are valoarea specificata
    heap[dimHeap-1] = val;
    // Restabilim proprietatea de heap
    urcaValoare(heap, dimHeap-1);
}

int main()
{
	FILE *in = fopen("gutui.in", "r");
	FILE *out = fopen("gutui.out", "w");
	struct pair p[MAX];
	int n, h, u, i, k = 0; 
	int temp_h, temp_g;
	fscanf(in, "%d%d%d", &n, &h, &u);
	for (i = 0; i < n; i++){
		fscanf(in, "%d%d", &temp_h, &temp_g);
		if (temp_h <= h)
		{
			p[k].inaltime = temp_h;
			p[k].greutate = temp_g;
			k++;
		}
	}
	n = k; //!! aici raman doar cu gutuile la care pot ajunge
	
	//rezolvare efectiva
	mergeSort(p, 0, n-1);
	int greutateMaxima=0; //solutia problemei
	/*
	inaltimea care se adauga crengilor,
	de la culegerea primei gutui
	*/
	int addedHeight=0;	
	//pentru toate gutuile, in ordine descrescatoare a inaltimilor
	for (i = n - 1; i >= 0; i--)
	{
		//verificam daca puteam culege gutuia(ajungem la ea)
		if (p[i].inaltime + addedHeight <= h)
		{
				adaugaValoare(heap, p[i].greutate);
				greutateMaxima += p[i].greutate;
				addedHeight += u; //actualizez addedHeight
		}
		else
		{
			//nu modific addedHeight
			/* verific daca aceasta gutuie cantareste mai mult 
				decat cea mai usoara gutuie culeasa pana acum
			*/
			if (p[i].greutate > minim(heap))
			{
				/* atunci inseamna ca trebuie inlocuita cu cea mai usoara
					gutuie culeasa pana in acest moment
				*/
				greutateMaxima -= minim(heap);
				greutateMaxima += p[i].greutate;
				extrageMinim(heap);
				adaugaValoare(heap, p[i].greutate);
			}
		}	
	}
	fprintf(out, "%d", greutateMaxima);
		
	//EXIT
	fclose(in);
	fclose(out);
	return 0;
}