Cod sursa(job #463394)

Utilizator simona.poilincaSimona Poilinca simona.poilinca Data 15 iunie 2010 17:04:21
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 2.82 kb
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>

using namespace std;

int N,H,U; // cu semnificatiile din enunt 

typedef struct { // definirea structurii gutuie cu campurile inaltime si greutate
		int h,g;
} gutuie;

gutuie *gutui; // vectorul de gutui

FILE *f,*g; // fisierele de intrare, respectiv iesire

bool comp(gutuie c1, gutuie c2) { // comparatorul pentru sortarea vectorului de gutui, descrescator dupa inaltime
	return c1.h > c2.h;
		return true;
}

bool compheap(int c1, int c2){ // comparatorul pentru heap : heapul folosit in algoritm va fi un minheap
	return c1 > c2;
}

int main(){
	
	int i,k,hc,j;
	int max = 0;
	int *heap;
	
	f = fopen("gutui.in","r");
	g = fopen("gutui.out","w");
	
	fscanf(f,"%d %d %d\n",&N,&H,&U);
	
	// alocari memorie
	heap = (int*)calloc(N,sizeof(int)); 
	gutui = (gutuie*)calloc(N,sizeof(gutuie));
	for(i=0;i<N;i++)
		fscanf(f,"%d %d\n",&gutui[i].h,&gutui[i].g);
		
	//sortare descrescator dupa inaltime
	sort(gutui,gutui+N,comp);
	
	//se elimina gutuile care sunt la inaltimi mai mari de H
	k=0;
	while(gutui[k].h>H)
		k++;
	for(i=0;i<N-k;i++)
		gutui[i]=gutui[i+k];
	N=N-k; // vectorul de gutui are acum N-k gutui, presupunand ca au fost k gutui mai inalte de inaltimea H
	
	
	// fac o transformare inaltimi - nivele
	// toate gutuile aflate intr-o marja (h,h-U) sunt situate pe acelasi nivel 
	// e totuna daca iau orice gutuie de pe acest nivel pentru ridicarea crengilor
	// nivelul cel mai de sus va fi nivelul 0, apoi nivelul 1, 2, etc.
	// calculez nivelele pentru toate gutuile
	k = 0; // nivelul curent
	hc = H; // inaltimea curenta
	i = 0; // contorul pentru vectorul de gutui
	
	while(i<N){
			while(gutui[i].h<=hc && gutui[i].h>(hc-U) && i<N){ // daca avem o gutuie intre hc si hc-U+1
				gutui[i].h = k; // ea se afla pe nivelul k
				i++;
			}
			hc = hc - U; // trecem la inaltimea corespunzatoare nivelului urmator
			k++; // creste nivelul
	}
	
	
	i = 0; // nivelul pe care ne aflam in momentul de fata
	k = 0; // dimensiunea heapului 
	
	for(j=0;j<N;j++){ // teta (N)
		if(gutui[j].h!=i) // daca ne aflam pe un nivel mai mare 
			i = gutui[j].h; // se actualizeaza i 
		if(k<=i){ // daca mai avem loc in heap
			heap[k] = gutui[j].g; // adaugam o gutuie
			k++; // crestem dimensiunea heapului
			push_heap(heap,heap+k,compheap); // ii actualizam proprietatea de heap - O(log k)
		}
		else // daca nu mai avem loc in heap
			if(heap[0]<gutui[j].g){ // daca gutuia din varful heapului e mai usoara decat gutuia curenta
				pop_heap(heap,heap+k,compheap); // o scoatem - O(log k)
				heap[k-1] = gutui[j].g; // o inlocuim
				push_heap(heap,heap+k,compheap); // actualizam proprietatea de heap - O(log k)
			}		
	}
	
	// Calcularea maximului
	for(i=0;i<k;i++)
		max = max + heap[i];
	// Afisarea rezultatului
	fprintf(g,"%d\n",max);
	
	// Inchiderea fisierelor 
	fclose(f);
	fclose(g);
	return 0;
	
}