Cod sursa(job #427108)

Utilizator stefansStefan-Gabriel Sicleru stefans Data 27 martie 2010 15:40:39
Problema Gutui Scor 10
Compilator c Status done
Runda teme_upb Marime 4.67 kb
/*
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);
}

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
        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 la gutuile la care pot ajunge
	/*
	printf("\n-------------\n");
	for (i=0;i<n;i++)
		printf("[%d %d] ",p[i].inaltime, p[i].greutate);
	*/
	mergeSort(p, 0, n-1);
	/*
	printf("\n");
	for (i=0;i <n; i++)
		printf("[%d %d] ",p[i].inaltime, p[i].greutate);
	printf("\n-------------\n\n");
	*/
	
	
	//rezolvare
		
	int greutateMaxima=0;
	int addedHeight=0;
	int min = p[n-1].greutate;
	
	for (i=n-1;i>=0;i--)
	{
		if (p[i].inaltime+addedHeight<=h)
		{
				
				adaugaValoare(heap, p[i].greutate);
				greutateMaxima += p[i].greutate;
				addedHeight += u; //actualizez addedHeight
				if (p[i].greutate < min)
					min = p[i].greutate;
		}
		else
		{
			//nu modific addedHeight
			//vad daca e mai mare decat minimul gutuilor de dinainte
			if (p[i].greutate > min )
			{
				//atunci inseamna ca trebuie INLOCUIT cu minimul, si a
				//actualizat minimul
				adaugaValoare(heap, p[i].greutate);
				greutateMaxima -= min;
				greutateMaxima += p[i].greutate;
				extrageMinim(heap);
			}
			
		}	
	}
	
	//afisez la ecran
	//printf("\ngreutate: %d\n", greutateMaxima);
	//printf("\n");
	//for (i=n-1;i>=0;i--)
		//printf("%d ",enabled[i]);
	fprintf(out,"%d",greutateMaxima);
	
	
	
	
	
	//EXIT
	fclose(in);
	fclose(out);
	return 0;
}