Pagini recente » Cod sursa (job #2024630) | Cod sursa (job #442692)
Cod sursa(job #442692)
# include <stdio.h>
#include <stdlib.h>
# define MAXW 2147483647
typedef struct gutuie { int h, w;} TGutuie;
void mergeS ( TGutuie** A ,int p, int q, int r )
{
int n1, n2, i, j, k;
n1 = q - p;
n2 = r - q;
TGutuie h1 [n1 + 1], h2[n2 + 1];
for ( i = 0; i < n1; i ++ )
h1[i] = (*A)[ p + i ];
for ( j = 0; j < n2; j++ )
h2[j] = (*A) [ q + j];
h1[n1].h = MAXW;
h2[n2].h = MAXW;
i = 0;
j = 0;
for ( k = p; k < r; k++ )
if ( h1[i].h <= h2[j].h )
{
(*A)[k] = h1[i];
i++;
}
else
{
(*A)[k] = h2[j];
j++;
}
}
void merge_sort ( TGutuie** A,int p,int r)
{
int q;
if ( p + 1 == r )
return;
q = ( p + r )/ 2;
merge_sort ( A, p, q );
merge_sort ( A, q, r );
mergeS ( A, p, q, r );
}
int main()
{
FILE *f1 = fopen ("gutui.in", "rt" );
FILE *f2 = fopen ("gutui.out", "wt");
if ( !f1 || !f2 )
{
fprintf ( f2, "eroare la deschiderea fisierelor ");
return -1;
}
int N, U, H, nr = 0, i, j, greutateMax = 0, inaltime = 0,k;
fscanf (f1, "%i%i%i",&N, &H, &U);
TGutuie *gutui, culese[N],a;
gutui = (TGutuie*)malloc(N*sizeof(TGutuie));
for ( i = 0; i < N; i++)
fscanf (f1, "%i%i", &(gutui[i].h), &(gutui[i].w) );
// sortare
merge_sort ( &gutui, 0, N );
/*for ( i = N-1; i >= 0; i--)
printf ("%i %i\n" , gutui[i].w, gutui[i].h);*/
//scanf("%i", &N);
for ( i = N-1; i >= 0; i-- )
{
if ( gutui[i].h + inaltime <= H )
{
culese[nr] = gutui[i];
inaltime = inaltime + U;
j = nr;
while ( j != 0 && culese[(j-1)/2].w > culese[j].w )
{
a = culese[( j - 1 )/2];
culese[(j-1)/2] = culese[j];
culese[j] = a;
j = ( j - 1 )/2;
}
nr++;
}
else
{
if ( culese[0].w < gutui[i].w )
{
culese[0] = gutui[i];
j = 0;
while ( 2*j + 1 < nr )
{
if( 2*j + 2 < nr )
if ( culese[2*j + 1].w <= culese[2*j + 2].w )
{
if ( culese[j].w > culese[2*j + 1].w)
{
a = culese[2*j +1];
culese[2*j +1] = culese[j];
culese[j] = a;
j = 2*j +1;
}
else
break;
}
else
{
if ( culese[j].w > culese[2*j + 2].w)
{
a = culese[2*j +2];
culese[2*j +2] = culese[j];
culese[j] = a;
j = 2*j +2;
}
else
break;
}
else
{
if ( culese[j].w > culese[2*j + 1].w)
{
a = culese[2*j +1];
culese[2*j +1] = culese[j];
culese[j] = a;
j = 2*j +1;
}
else
break;
}
}
}
}
/*for ( k = 0; k < nr; k++ )
printf ( "%i ",culese[k].w);
printf ( "\n");
*/
}
for ( i = 0; i < nr; i++ )
greutateMax = greutateMax + culese[i].w;
fprintf(f2,"%i", greutateMax);
free(gutui);
fclose(f1);
fclose(f2);
//getch();
return 0;
}