Pagini recente » Cod sursa (job #425943) | Cod sursa (job #1148622) | Cod sursa (job #574279) | Cod sursa (job #463065) | Cod sursa (job #463080)
Cod sursa(job #463080)
/* Tema 1 - PA
* Ene Adriana- Mihaela
* 325CA
*/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <vector>
using namespace std;
int N ;
int H , U;
typedef struct gutui // structura cu gutuile de pe fiecare nivel
{
int *g;
int nr;
} GUTUI;
GUTUI *G;
int nr_nivele;
int nivel( int h )
{
return ( H - h ) / U;
}
void citire() // citirea din fisier si formarea structurii cu gutui
{
int i , h , gre , niv , n ;
nr_nivele = 0;
FILE *f = fopen ( "gutui.in" , "r" ) ;
fscanf( f , "%d%d%d", &N , &H , &U) ;
G = ( GUTUI * ) malloc ( ( H / U + 1 ) * sizeof ( GUTUI ) ) ;
for ( i = 0 ; i < H / U ; i++ )
{
G[i].g = NULL ;
G[i].nr = 0;
}
for ( i = 0 ; i < N ; i++ )
{
fscanf ( f , "%d%d" , &h , &gre ) ;
niv = nivel ( h );
n = G[niv].nr;
G[niv].g = ( int * ) realloc ( G[niv].g , ( n + 2 ) * sizeof ( int ) ) ;
G[niv].g[n] = gre;
G[niv].nr = G[niv].nr + 1;
}
nr_nivele = H / U;
if ( H % U != 0)
nr_nivele++;
fclose ( f );
}
int compar (const void * x, const void * y) // fumctie de comparare pentru ordonare descrescatoare la QSORT
{
return ( * ( int * ) y - * ( int * ) x );
}
bool compare(unsigned int x , unsigned int y) // functie pentru inplace_merge
{
return x > y;
}
void rezolva()
{
int suma = 0;
int i , j , k , l = 0;
vector<int> max;
for (i = 0 ; i < nr_nivele ; i++)
qsort ( G[i].g , G[i].nr , 4 , compar );
for (i = 0 ; i < nr_nivele ; i++) // pentru fiecare nivel unde nivelele sunt 0 1 2 3.. de sus in jos
{
j = i + 1;
if (G[i].nr != 0)
{
for (k = 0 ; k < j ; k++)
if ( ( G[i].nr - k ) > 0 )
max.push_back(G[i].g[k]);
else
break;
inplace_merge ( max.begin(), max.end() - k, max.end(), compare ); //sortare pentru a lua cele mai mari j gutui
max.resize(j);
}
}
for ( i = 0 ; i < (int) max.size() ; i++)
suma = suma + max[i];
FILE *f = fopen ( "gutui.out" , "w" ) ; //scriere in fisier
fprintf ( f , "%d\n" , suma );
fclose(f);
}
int main()
{
citire();
rezolva();
return 0;
}