Cod sursa(job #438497)

Utilizator mirunici2389Miruna Popescu mirunici2389 Data 10 aprilie 2010 20:24:01
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 1.81 kb
#include<stdio.h>
#include<stdlib.h>

//structura celula pt lista dublu inlantuita
typedef struct cel
{
	int gre;
	cel * next;
	cel * pre;
}celula;

//structura gutuie
typedef struct gut
{
	int nivel;
	int greutate;
	int inaltime;
}gutui;

//fct de comparare pt qsort - sorteaza gutui in fct de inaltime
int comparator2(const void * a,const void *b)
{
	return (*((gutui *)b)).inaltime-(*((gutui *)a)).inaltime;
}

//fct intoarce pozitia pe care se gaseste minimul dintr-un vector
int poz_minim(int vector[], int n)
{
	int i;
	int poz = 0;
	int min = vector[0];
	for (i=0;i<n;i++)
	{
		if (vector[i] < min)
		{
			min = vector[i];
			poz = i;
		}
	}
	return poz;
}

int main()
{
	FILE *f=NULL,*g=NULL;
	int N,H,U;
	int i,j,n,niv,pozitie;
	int greutate_culeasa=0;
	gutui *mat;
	
	//citesc datele de intrare si calculez nivelele pe care sunt asezate gutuile
	f=fopen("gutui.in","rt");	
	fscanf (f,"%i%i%i",&N,&H,&U);
	mat = (gutui*)malloc(N*sizeof(gutui));
	for(i=0;i<N;i++)
	{
		fscanf(f,"%i%i",&(mat[i].inaltime),&(mat[i].greutate));
		if (mat[i].inaltime > H ) mat[i].nivel = 0;
		else mat[i].nivel = ((H-mat[i].inaltime) / U )+1;
		
	}
	
	//sortez dupa inaltime
	qsort(mat, N, sizeof(gutui), comparator2);
	
	//creez un vector cu greutatile gutuilor pe care le culeg
	
	int *greutati=(int*)malloc(N*sizeof(int));
	i=0;
	niv=0;
	for(j=0;j<N;j++)
	{
		if (mat[j].nivel>niv) 
		{
			greutati[i]=mat[j].greutate;
			i++;
			niv++;
		}
		else
		{
			pozitie=poz_minim(greutati,i);
			if(mat[j].greutate > greutati[pozitie]) greutati[pozitie] = mat[j].greutate;
		}
	}
	n=i;
	
	//scriu datele de iesire
	g=fopen("gutui.out","wt");
	for (i=0;i<n;i++)
		greutate_culeasa += greutati[i];
	fprintf(g,"%i",greutate_culeasa);
	
	fclose(f);
	fclose(g);
	return 0;
}