Cod sursa(job #439506)

Utilizator gabi.boteaBotea Gabriela gabi.botea Data 11 aprilie 2010 16:43:28
Problema Gutui Scor 100
Compilator c Status done
Runda teme_upb Marime 2.89 kb
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#define CHILD(node) ((node) * 2 + 1)          //copilul din stanga 

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

typedef GUTUIE (*comp)(const void*,const void*);



int cresc (const void * a, const void * b)
{
	if ((*(GUTUIE*)a).h == (*(GUTUIE*)b).h)	
		return -((*(GUTUIE*)a).g - (*(GUTUIE*)b).g); 
	 return ((*(GUTUIE*)a).h - (*(GUTUIE*)b).h); 	
}

unsigned int parent(unsigned int i){
	if (i % 2 == 0) return (i/2 - 1);
		else return i/2;
}

void insert(unsigned int g, unsigned int *heap, unsigned int i){
heap[i] = g;
unsigned int aux;
while ((i > 0) && (heap[i] < heap[parent(i)])) {
		aux = heap[parent(i)];
		heap[parent(i)] = heap[i];
		heap[i] = aux;
		i = parent(i);
		}  
}

void minheapify(unsigned int *heap, unsigned int i, unsigned int n){

	while ( CHILD(i) < n){
		unsigned int child = CHILD(i);
		if (child + 1 < n && heap[child] > heap[child+1])    //alegem cel mai mic copil
 			child++;
		
		if (heap[i] > heap[child]){		//mutam cel mai mic nod in radacina
			unsigned int temp = heap[i];
			heap[i] = heap[child];
			heap[child] = temp;
		}
	++i;
	}
}


int main(){

int N,i;
unsigned int H,U,level,sum,k,x;

GUTUIE *g;
FILE *f,*o;

f = fopen("gutui.in","r");
o = fopen("gutui.out","w");

fscanf(f,"%d",&N);
fscanf(f,"%d",&H);
fscanf(f,"%d",&U);

g = malloc(N * sizeof (GUTUIE));


for (i = 0;i < N;i++){
	fscanf(f,"%d",&x);
	if (H >= x) 
		g[i].h = (H-x)/U + 1; //cream nivelele in structura (sunt mai usor de utilizat decat inaltimile brute)
	fscanf(f,"%d",&g[i].g);
	}

qsort(g, N, sizeof(GUTUIE), cresc); //sortam structura crescator pe nivel si la nivele egale decrescator dupa greutate
				    //complexitate Theta(n*logn);

unsigned int * heap = (unsigned int *)calloc(N,sizeof(unsigned int));


level = 0;  //nr maxim de gutui care poate fi cules la un nivel

sum = 0;
	
k = 0;   //retinem in k nr de gutui din heap
for (i = 0; i < N; i++){                   
	if (level < g[i].h) {//daca ajungem la un nivel nou
		level = g[i].h;   //il actualizam
		insert(g[i].g, heap, k); //inseram gutuia de pe noul nivel in heap (Theta(logn))
		k++;		//actualizam nr de gutui din heap
		sum += g[i].g;  //o adunam la suma
		}
	else if (level == g[i].h){	//daca intalnim o gutuie pe acelasi nivel
       		if (k < level){  //daca in heap mai este loc pentru gutui
			insert(g[i].g, heap, k); //inseram o gutuie in heap pe pozitia k  (Theta(logn))
			k++;         		
			sum += g[i].g;   	 // si adunam la suma
			}
			   
		else {				//daca am atins in heap nr maxim de gutui pentru un nivel
			if (heap[0] < g[i].g) {   		//daca minimul din heap e mai mic decat greutatea gutuii actuale
				sum = sum - heap[0] + g[i].g;	//actualizam suma
				heap[0] = g[i].g;		//inseram in radacina si apoi coboram
				minheapify(heap, 0, k);				//(Theta(logn)) 
					}
		     }
			
		}
}	 

fprintf(o,"%d\n",sum);


fclose(f);
fclose(o);

return 0;
}