Pagini recente » Cod sursa (job #463032) | Cod sursa (job #1437827) | Cod sursa (job #574407) | Cod sursa (job #2958948) | Cod sursa (job #463339)
Cod sursa(job #463339)
#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;
}