Cod sursa(job #423461)

Utilizator vdobrotaDobrota Valentin Eugen vdobrota Data 23 martie 2010 21:39:56
Problema Gutui Scor 100
Compilator c Status done
Runda teme_upb Marime 2.79 kb
// Dobrota Valentin-Eugen, 324CA, PA, Tema1, Prob2 - Gutui, 2009-2010

#include<stdio.h>
#define MAXSIZE 100001

// Inaltimile
int inaltime[MAXSIZE];
// Greutatile
int greutate[MAXSIZE];
/*
	precedent[i]==k <=> toate locurile de la k+1 la i inclusiv sunt ocupate deja
	nu este obligatoriu ca locul k sa fie liber
	precedent[i]==0 <=> locul i este liber.
	Intuitiv, precedent[i] tine minte cel mai apropiat loc liber din stanga fata de i.
*/
int precedent[MAXSIZE];

// Interschimba valorile din locatii de memorie
void interschimba(int *a, int *b)
{
   int t;
   t = *a;
   *a = *b;
   *b = t;
}

// Sorteaza greutatile si inaltimile dupa greutate
void sorteaza(int m, int n)
{
	int cheie,i,j,k;
	if( m < n)
	{
		k = (m+n)/2;
		interschimba(&greutate[m],&greutate[k]);
		interschimba(&inaltime[m],&inaltime[k]);
		cheie = greutate[m];
		i = m+1;
		j = n;
		while(i <= j)
		{
			while((i <= n) && (greutate[i] <= cheie))
				i++;
			while((j >= m) && (greutate[j] > cheie))
				j--;
			if( i < j)
			{   
				interschimba(&greutate[i],&greutate[j]);	         
				interschimba(&inaltime[i],&inaltime[j]);
			}
		}
		interschimba(&greutate[m],&greutate[j]);
		interschimba(&inaltime[m],&inaltime[j]);                        
		sorteaza(m,j-1);
		sorteaza(j+1,n);
	}
}

int main()
{
	// Declarari:
	int n; // Numarul de gutui
	int h; // Inaltimea maxima
	int u; // Inaltimea pierduta la fiecare pas
	int i,j,k, start, val; // variabile auxiliare
	int suma=0; // suma gutuilor culese
	int stiva[MAXSIZE]; // stiva de imbunatatire a vectorului precedent[]
	freopen("gutui.in","r",stdin); // fisier intrare
	freopen("gutui.out","w",stdout); // fisier iesire
	
	// Citiri
	scanf("%d %d %d",&n,&h,&u);
	for(i=1;i<=n;i++)
		scanf("%d %d",&(inaltime[i]),&(greutate[i]));
		
	// Sortare
	sorteaza(1,n);
	
	// Greedy
	for(i=n;i>0;--i)
	{
		/*
			(1)Voi retine in start primul loc liber la stanga prin parcurgerea lui precedent[].
			(2)Voi retine in stiva toate locurile ocupate prin care am trecut.
			(3)Voi actualiza precedent[] pentru toate locurile din stiva cu valoarea aflata.
		*/		
		
		/*
			Incep cu locul cel mai favorabil si daca e ocupat ma mut la stanga cat de putin pot
			folosing garantia data de vectorul precedent[].
		*/
		
		start=1+(h-inaltime[i])/u;
		k=1;
		stiva[k]=start;		
		while(precedent[start] && start>0)
		{		
			start=precedent[start];//(1)
			stiva[++k]=start;//(2)
		}		
		if(start>0)		
		{
			if(start!=1)
				if(precedent[start-1])
					val=precedent[start-1];
				else
					val=start-1;
			else
				val=-1;
			// val retine acum cel mai apropiat loc liber din stanga pentru _toate_
			// pozitiile din stiva[]
			for(j=1;j<=k;j++)
				precedent[stiva[j]]=val;//(3)
			// Fiind greedy, aleg sa iau aceasta gutuie si o adaug la suma luata.
			suma+=greutate[i];
		}
	}	
	
	// Afisare solutie	
	printf("%d\n",suma);
return 0;
}