Cod sursa(job #440582)

Utilizator kp_itchyAlexandra kp_itchy Data 12 aprilie 2010 10:48:22
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 2.53 kb
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;

typedef struct {
	int greutate;
	int inaltime;
} gutuie;

//interschimba 2 elemente din vectorul de gutui
void swap(gutuie *a, gutuie *b) {
	gutuie aux;
	aux=*a;
	*a=*b;
	*b=aux;
}

//auxiliar pentru functia de sortare quicksort
int choose_pivot(int i, int j) {
	return ((i+j)/2);
}

//sorteaza descrescator in functie de greutate in vectorul de gutui
void qsort(gutuie *g, int m, int n) {	
	int key,i,j,k;
	if (m<n)
		{
			k=choose_pivot(m,n);
			swap(&g[m],&g[k]);
			key=g[m].inaltime;
			i=m+1;
			j=n;
			while (i<=j)
				{
				while ((i<=n)&&(g[i].inaltime>=key))
					i++;
				while ((j>=m) &&(g[j].inaltime<key))
					j--;
				if (i<j)
					swap(&g[i],&g[j]);
				}
			swap(&g[m],&g[j]);
			qsort(g,m,j-1);
			qsort(g,j+1,n);
		}
	}
//comparator util pentru pop_heap si push_heap, reprezentand functia de pozitionare a unei gutui in heap
bool comparatorGreutate(gutuie a, gutuie b) {
	return (a.greutate>b.greutate);
	}
	
int main() {
	//DECLARARI VARIABILE
	int n,h,u,i,gt=0;
	FILE *in=fopen("gutui.in","r");
	FILE *out=fopen("gutui.out","w");
	vector<gutuie> heap;
		
	fscanf(in,"%u%u%u",&n,&h,&u);
	
	//ALOCARE DE MEMORIE
	gutuie *g=(gutuie*)malloc(n*sizeof(gutuie));
	
	//CITIRE DIN FISIER INTRARE SI INITIALIZARE ARRAY de gutui g
	for (i=0;i<n;i++)
		fscanf(in,"%u%u",&g[i].inaltime,&g[i].greutate);
		
	//sortare vector de gutui dupa inaltime
	qsort(g,0,n-1);
	
	//adaugare prima gutuie
	heap.push_back(g[0]);
	
	for (i=1;i<n;i++) {
		//daca nu mai pot fi adaugate elemente in heap si gasim o gutuie cu o greutate mai mare decat varful heap-ului
		if (heap.size()==(1+(h-g[i].inaltime)/u) && heap.front().greutate<g[i].greutate) {
			//extrage ultimul element al heap-ului, considerat a fi reprezentat de gutuia cu cea mai mica greutate
			pop_heap(heap.begin(),heap.end(),comparatorGreutate);
			heap.pop_back();
			//adauga noua gutuie cu greutatea mai mare decat varful heap-ului
			heap.push_back(g[i]);
			push_heap(heap.begin(),heap.end(),comparatorGreutate);
		}
		//daca inca se mai pot adauga gutui in heap
		else if (heap.size()!=(1+(h-g[i].inaltime)/u)) {
				//adauga gutuia i si reface structura heap-ului
				heap.push_back(g[i]);
				push_heap(heap.begin(),heap.end(),comparatorGreutate);
		}
	}
	
	//calculam greutatile gutuilor ramase in heap
	for (i=0;i<heap.size();i++)
		gt+=heap[i].greutate;
	
	
	//AFISAREA REZULTATULUI IN FISIERUL DE IESIRE
	fprintf(out,"%u\n",gt);	
	
	//ELIBERARE MEMORIE
	free(g);
	
	//INCHIDERE FISIERE INTRARE/IESIRE
	fclose(in);
	fclose(out);
	
	return 0;
	}