Cod sursa(job #463339)

Utilizator simona.poilincaSimona Poilinca simona.poilinca Data 15 iunie 2010 02:40:53
Problema Gutui Scor 80
Compilator c Status done
Runda teme_upb Marime 2.17 kb
#include<stdio.h>
#include<stdlib.h>
#define N 100000
FILE *fin, *fout;
long long int n,h,u;
long long int aleg[N];

/* structura de tip gutuie care contine greutatea gutuii si nivelul la care se afla*/
typedef struct gutuie{
	long long int nv;//nivel
	long long int g; //greutate
	} Gutuie;
//variabila pom contine toate gutuile de tipul structura
Gutuie *pom;

//functie comparare pentru qsort
int comp(const void * a, const void * b) {

	if ((*(Gutuie*) b).nv - (*(Gutuie*) a).nv < 0) return -1;
	else 
	if ((*(Gutuie*) b).nv - (*(Gutuie*) a).nv == 0) return 0;
	else
	return 1;
}

int main(void) 
{
	/* fisiere intrare iesir */
	fin = fopen("gutui.in", "r");
	fout = fopen("gutui.out", "w");
	long long int i,j;
	long long int inaltimegutuie;
	//citire N H U din fisier
	fscanf(fin, "%lld %lld %lld", &n, &h, &u);
	
	long long int pas=0;
	long long int aleg[n],min,ales;
	long long int suma=0;
	//alocare memorie
	pom=(Gutuie *) calloc (n,sizeof(struct gutuie));
	//citirea pomului din fisier
	for (i = 0; i < n; i++) {
		//citesc din fisier inaltime gutuie + greutate
		fscanf(fin, "%lld %lld", &inaltimegutuie, &(pom[i].g));
		//transform inaltime gutuie + inaltime pas in nivel
		pom[i].nv=(h-inaltimegutuie)/u + 1;
	}
	//sortez in functie de nivel
	qsort(pom,n,sizeof(struct gutuie),comp);
	//algoritm :
	for(i=n-1;i>=0;i--)
	{
		//daca pas < nivelul curent atunci trec la nivelul curent si aleg prima gutuie de pe nivelul vurent
		if( pas < pom[i].nv )
			aleg[++pas]=pom[i].g;
		else
		//daca pas = nivelul curent atunci caut sa maximizez vectorul de alegeri prin inlocuirea
		//greutatii minime din vect de alegeri cu greutatea maxima de pe nivelul curent
			if ( pas == pom[i].nv )
			{
				min=aleg[pas];
				ales=pas;
				//caut minim in vectorul de alegeri
				for(j=1;j<=pas;j++)
					if( min > aleg[j] ) 
					{ 
						min=aleg[j];
						ales=j;
					}
				//inlocuiesc daca pe niv curent am gutuie mai mare decat in minimul din vect de alegeri
				if(pom[i].g > aleg[ales]) aleg[ales]=pom[i].g;
							
			}
	}
	//calculez suma maxma adunand cele mai bune alegeri  
	for(i=1;i<=pas;i++)
		suma=suma+aleg[i];
	//printez solutia
	fprintf(fout,"%lld\n",suma);		
	fclose(fin);
	fclose(fout);
	return 0;
}