Pagini recente » Cod sursa (job #2661479) | Cod sursa (job #1438288) | Cod sursa (job #1125069) | Cod sursa (job #2663428) | Cod sursa (job #463285)
Cod sursa(job #463285)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <queue>
using namespace std;
struct gutuie {
unsigned int height;
unsigned int weight;
};
//clasa comparator folosita la ordonarea vectorului de gutui dupa inaltimea si greutate
class compare {
int hmax, nivel;
public:
compare(int i, int j) : hmax(i), nivel(j) {};
bool operator()(gutuie x, gutuie y) {
return (((hmax - x.height) / nivel) + 1 < ((hmax - y.height) / nivel) + 1)
|| (!(((hmax - y.height) / nivel) + 1 < ((hmax - x.height) / nivel) + 1) && (x.weight > y.weight));
}
};
int main() {
int n;
unsigned int h, u;
gutuie g;
vector<gutuie> gutui;
vector<int> nivel;
//priority queue care satisface proprietatea de min-heap
priority_queue< int, vector<int>, greater<int> > best;
//citirea datelor de intrare
ifstream fin("gutui.in");
fin >> n >> h >> u;
for (int i = 0; i < n; i++) {
fin >> g.height >> g.weight;
gutui.push_back(g);
}
fin.close();
//ordonam vectorul de gutui dupa inaltime si greutate
sort(gutui.begin(), gutui.end(), compare(h, u));
//construim vectorul nivel care contine pt fiecare gutuie nivelul pe care se afla
for (int i = 0; i < n; i++)
nivel.push_back(((h - gutui[i].height) / u) + 1);
nivel.push_back(nivel[n - 1] + 1);
int i = 0;
int niv = nivel[0];
int ad = 0;
//pt fiecare gutuie
while (i < n) {
//daca este pe nivelul curent si nu am adaugat maximul posibil de gutui
if (nivel[i] == niv && ad < niv) {
//adaugam gutuia in p_queue
best.push(gutui[i].weight);
ad++;
//trunchiem best la numarul maxim de gutui care se pot adauga de pe nivelul curent
if (best.size() > niv) {
best.pop();
}
//daca urmatoarea gutuie e pe un nivel mai mare
if (nivel[i + 1] > niv) {
//incrementam nivelul curent
niv = nivel[i + 1];
ad = 0;
}
i++;
}
//daca este pe nivelul curent dar am adaugat maximul posibil de gutui deja
else if (nivel[i] == niv && ad == niv) {
//facem aceeasi verificare ca mai sus si trecem mai departe
if (nivel[i + 1] > niv) {
niv = nivel[i + 1];
ad = 0;
}
i++;
}
}
//calculam greutatea maxima
unsigned int gmax = 0;
while (best.size() > 0) {
gmax += best.top();
best.pop();
}
//afisam
ofstream fout("gutui.out");
fout << gmax << endl;
fout.close();
return 0;
}