Pagini recente » Cod sursa (job #1781019) | Cod sursa (job #658379) | Cod sursa (job #711895) | Cod sursa (job #845941) | Cod sursa (job #441188)
Cod sursa(job #441188)
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
// h - inaltimea gutuiei
// g - greutatea gutuiei
// disp - disponibilitatea gutuiei
struct Gutuie{
long int h,g,disp;
};
int comparaGutui(Gutuie g1,Gutuie g2){
return g1.h > g2.h;
}
int main(){
FILE *fin,*fout;
long int n,h,u,i,gMax=0,dispCurenta;
vector<long int> greutatiDisp;
//CITIRE DATE DE INTRATRE
fin = fopen("gutui.in","rw");
fscanf(fin,"%ld %ld %ld",&n,&h,&u);
vector<Gutuie> gutui(n);
for (i=0;i<n;i++){
fscanf(fin,"%ld %ld",&(gutui[i].h),&(gutui[i].g));
gutui[i].disp = (h-gutui[i].h)/u; //stabilire life-span
}
//SORTARE - conform specificatiilor sort din
sort(gutui.begin(),gutui.end(),comparaGutui);
/*
* Disponibilitatea unei gutui = numarul de ridicari cu U a gutuiei fara a ajunge la o inaltime inaccesibila (>H)
*
* Avand gutuile aranjate dupa disponibilitate incepem rezolvarea decizand ce gutuie alegem in ordine inversa.
* Alegem prima data ultima gutuie pe care o vom culege, a doua oara penultima etc.
*
* Stocam greutatile gutuilor cu aceeasi disponibilitate intr-un vector greutatiDisp pe care il aranjam ca un heap
* Astfel primul element va fi intotdeauna cel mai mare - folosirea heapului ne ajuta sa avem o complexitate
* mai mica deoarece plasarea unui element in heap se realizeaza in O(log n) unde n este adancimea heapului
*
* Din acest vector (gutui Disp) scoatem dupa trecerea la un nou nivel si actualizarea vectorului maximul, pe care il adaugam la gMax
* Maximul nu trebuie neaparat sa fie de la elementele cu disponibilitatea curenta ci poate fi din elementele cu disponibilitate anterioara
*
*/
dispCurenta = gutui[n-1].disp; //ultimul element din vector va avea disponibilitatea cel mai mare
while ((gutui.size() or greutatiDisp.size()) and dispCurenta != -1){
//actualizare vector (heap) de gutui disponibile prin adaugarea gutuilor cu aceeasi disponibilitate
while (gutui.size() and gutui.back().disp == dispCurenta) {
greutatiDisp.push_back(gutui.back().g);
push_heap(greutatiDisp.begin(), greutatiDisp.end()); // refac ordinea de heap
gutui.pop_back(); //scot elementul din lista
}
dispCurenta --;
// adaugare cea mai mare greutate disponibila
if (greutatiDisp.size()){
gMax += greutatiDisp.front();
pop_heap(greutatiDisp.begin(),greutatiDisp.end()); // rearanjeaza heapul - cea mai mare greutate este ultima
greutatiDisp.pop_back(); // scot greutatea
}
}
// SCRIERE GREUTATE MAXIMA IN FISIERUL DE IESIRE
fout = fopen("gutui.out","wt");
fprintf(fout,"%ld",gMax);
//INCHIDERE FISIERE
fclose(fin);
fclose(fout);
return 0;
}