Pagini recente » Cod sursa (job #2923200) | Cod sursa (job #1826878) | Cod sursa (job #423461)
Cod sursa(job #423461)
// 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;
}