Pagini recente » Cod sursa (job #2538408) | Cod sursa (job #303294) | Cod sursa (job #411617) | Cod sursa (job #3260582) | Cod sursa (job #440295)
Cod sursa(job #440295)
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
int main()
{
FILE *f, *g;
long int n;
uint32_t h, u;
uint32_t hg[100000], wg[100000], v_suma[100000], v_h[100000], v[100000]; //v_suma este folosit pentru a memora solutiile partiale ale problemei, v_h este folosit pentru a tine evidenta inaltimii pana la care putem sa culegem in momentul curent
long int i = 0;
long int j;
long int x = 0;
int ok;
uint32_t aux;
uint32_t min, max=0;
f = fopen( "gutui.in", "r" );
g=fopen( "gutui.out", "w" );
fscanf( f, "%ld", &n );
fscanf( f, "%d", &h );
fscanf( f, "%d", &u );
while(i<n)
{
fscanf( f, "%d", &hg[i] );
fscanf( f, "%d", &wg[i] );
if ( hg[i] > h ) //conditie necesara ca programul sa nu citeasca si gutuile la inaltimi mai mari de h
{
wg[i] = 0;
i--;
n--;
}
i++;
}
for ( i = n - 1; i >= 0; i-- ) //bubble sort ordoneaza descrescator gutuile dupa inaltime
{
for( j = 1; j <= i; j++ )
if(hg[j-1]<hg[j])
{
aux = hg[j - 1];
hg[j - 1] = hg[j];
hg[j] = aux;
aux = wg[j - 1];
wg[j - 1] = wg[j];
wg[j] = aux;
}
if( max < wg[n - i - 1] ) //se determina greutatea maxima a unei gutui
max = wg[n - i - 1];
v[n - i]=0;
}
v_suma[0] = wg[0]; //initializam prima solutie partiala cu greutatea gutuii care se afla cel mai sus si inaltimea curenta cu inaltimea maxima minus u
v_h[0] = h - u;
for( i = 1; i <= n; i++ )
{
ok = 0;
if( hg[i] <= v_h[i - 1] ) //daca gutuia curenta se afla la o inaltime mai mica decat cea maxima curenta adunam greutatea ei la solutia partiala anterioara
v_suma[i] = v_suma[i - 1] + wg[i];
else
{
min = max; //daca gutuia curenta se afla mai sus decat inaltimea maxima curenta programul determina gutuia cu greutate minima
for( j = 0; j < i; j++ ) //dintre gutuile de pana atunci si daca aceasta greutate minima este mai mica decat greutatea curenta atunci
if( v[j] == 0 ) //inlocuim in solutia partiala anterioara gutuia cu greutate minima cu gutuia curenta, altfel solutia partiala ramane la fel
if( min > wg[j] )
{
min = wg[j];
x = j;
}
if( min < wg[i] )
{
v[x] = 1; //vectorul v are rolul de a tine minte gutuile care nu vor face parte din solutia finala dar sunt intalnite in calcularea solutiilor partiale
v_suma[i] = v_suma[i - 1] + wg[i] - min;
}
else
{
v[i] = 1;
v_suma[i] = v_suma[i - 1];
}
ok = 1;
}
if(( v_h[i - 1] > 0 )&&( ok == 0 ))
v_h[i] = v_h[i - 1] - u;
else //variabila ok ia valoare 1 in cazul in care nu este necesara scadera inaltimii maxime in pasul curent
v_h[i] = v_h[i - 1];
}
fprintf( g, "%d", v_suma[n] );
fclose(f);
fclose(g);
return 0;
}