Pagini recente » Cod sursa (job #730354) | Cod sursa (job #2252030) | Cod sursa (job #1918120) | Cod sursa (job #2729571) | Cod sursa (job #439915)
Cod sursa(job #439915)
#include <iostream>
#include <stdlib.h>
#include <fstream>
#include <queue>
using namespace std;
typedef struct gs{ /* structura unei gutui */
unsigned int ng; /* nivel gutuie - in functie de h si u se pot determina anumite nivele, astfel incat
dupa ce a fost culeasa o gutuie vor disparea toate gutuile de pe cel mai inalt nivel curent */
unsigned int gg; /* greutate gutuie */
} gs;
unsigned int h,u; /* h = inaltimea maxima, u = cu cat se ridica crengile dupa ce a fost culeasa o gutuie */
unsigned int n; /* numarul de gutui */
gs *gt; /* vectorul de gutui */
unsigned int nr_luate = 0;
unsigned int p; /* numarul de gutui care se pot lua; daca este posibil am dori sa luam primele p gutui ca greutate */
unsigned int gmax = 0; /* greutatea maxima */
unsigned int nivmax = 0; /* nivelul maxim */
/* coada de prioritati ce va contine greutatile gutuilor luate, in ordine crescatoare */
priority_queue<unsigned int, std::vector<unsigned int>, std::greater<unsigned int> > q;
/* functia de comparare pentru qsort
sortam gutuile in ordine crescatoare a nivelului pe care se afla */
int compare (const void * a, const void * b)
{
if ( ((gs *)b)->ng < ((gs *)a)->ng ){
return 1;
}
if ( ((gs *)b)->ng > ((gs *)a)->ng ){
return -1;
}
return 0;
}
/* functia care determina greutatea maxima ce poate fi culeasa */
int get_gmax(){
unsigned int i;
/* se parcurg toate gutuile */
for( i = 0; i < n; i++ ){
if( gt[i].ng > nr_luate ){ /* daca gutuia curenta se poate lua atunci o culegem */
q.push ( gt[i].gg ); /* se adauga la gutuile culese */
gmax = gmax + gt[i].gg;
nr_luate ++;
}
else{
/* daca gutuia curenta are o greutate mai mare decat cea mai usoara gutuie culeasa
atunci interschimbam cele doua gutui */
if(gt[i].gg > q.top()){
gmax = gmax - q.top(); /* renuntam la gutuia cu greutate minima */
q.pop();
q.push ( gt[i].gg ); /* adaugam noua gutuie */
gmax = gmax + gt[i].gg;
}
}
}
return 0;
}
/* citeste datele initiale */
int read_vec(){
ifstream fin;
unsigned int i;
unsigned int hg, o; /* hg = inaltime gutuie, o = offset al inaltimii */
/* adaugam acest offset pentru ca am dori ca inaltimea maxima sa fie de forma ( const * u - 1 ),
pentru a putea separa in mod corect nivelele, asadar trebuie sa modificam toate inaltimile in mod
corespunzator, adunand acest offset; astfel nivelul pentru o gutuie aflata la inaltimea hg va fi
egal cu ( hg / u ) */
fin.open("gutui.in",ios::in);
fin >> n;
fin >> h;
fin >> u;
o = u - ( h % u ) - 1; /* calculam offsetul pentru inaltime */
h = h + o; /* inaltimea maxima */
gt = (gs *)malloc( n * sizeof( gs )); /* vectorul de gutui */
nivmax = h / u; /* nivelul maxim */
for( i = 0; i < n; i++ ){
fin >> hg;
fin >> gt[i].gg;
if( hg > h ){ /* daca gutuia nu este accesibila nici macar la primul pas, o ignoram */
i--;
n--;
continue;
}
hg = hg + o; /* inaltimea gutuii */
gt[i].ng = nivmax + 1 - ( hg / u ); /* nivelul gutuii => dupa cati pasi mai poate fi culeasa o gutuie */
}
qsort (gt, n, sizeof(gs), compare); /* sortam gutuile crescator in functie de nivel */
fin.close();
return 0;
}
/* scrie solutia */
int write_sol(){
ofstream fout;
fout.open("gutui.out",ios::out);
fout << gmax;
fout.close();
return 0;
}
int main(){
read_vec();
get_gmax();
write_sol();
return 0;
}