Pagini recente » Cod sursa (job #264306) | Cod sursa (job #463163) | Cod sursa (job #2265679) | Cod sursa (job #3186933) | Cod sursa (job #463278)
Cod sursa(job #463278)
//NISTOR RUXANDRA
//321 CA
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <queue>
using namespace std;
class Fruit
{
public:
//constructorii ptr clasa Fruit
Fruit() {};
Fruit(int x, int y) { height = x; weight = y; }
bool operator<(const Fruit&) const;
int get_height() const { return height; }
int get_weight() const { return weight; }
private:
int height, weight;
};
//functia de comparare intre doua elemente Fruit
bool Fruit::operator<(const Fruit& right) const
{
return height < right.height;
}
class Fruit2
{
public:
//constructorii ptr clasa Frui
Fruit2() {};
Fruit2(int x, int y) { height = x; weight = y; }
bool operator<(const Fruit2&) const;
int get_height() const { return height; }
int get_weight() const { return weight; }
private:
int height, weight;
};
//functia de comparare intre doua elemente Fruit2
bool Fruit2::operator<(const Fruit2& right) const
{
return weight > right.weight;
}
int main()
{
unsigned int h, u, height, weight;
int n, i;
Fruit x;
Fruit2 y;
priority_queue <Fruit> pq;
priority_queue <Fruit2> pq2;
//se citesc datele din fisier
FILE *fin = fopen("gutui.in", "r");
fscanf(fin, "%d", &n);
fscanf(fin,"%u", &h);
fscanf(fin, "%u", &u);
//se pun gutuile intr-o coada prioritara in functie de inaltime
for(i = 0; i < n; i++){
fscanf(fin, "%u %u", &height, &weight);
x = Fruit(height, weight);
pq.push(x);
}
//ok-ul retine cate gutui mai trebuie bagate in coada de prioritati dupa greutate (pq2)
//no este momentul dew timp curent
int ok = 1, no = 1;
unsigned int greutate = 0, ming;
//cat timp mai sunt elemente care nu s-au verificat in coada
while (!pq.empty()) {
//se retin inaltimea si greutatea
height = pq.top().get_height();
weight = pq.top().get_weight();
//daca gutuia dispare la momentul no si este prima
if(height + no * u > h && ok > 0){
//gutuia este bagata intr-o coada de prioritati pq2- dupa greutati-, ordonata crescator dupa inaltime
y = Fruit2(height, weight);
pq2.push(y);
//se scade numarul de gutui care trebuie bagate in coada pana la mom no
ok --;
//se scoate elementul din coada1 -dupa inaltimi-
pq.pop();
}
else
//daca ptr mom no s-a bagat deja o gutuie
if(!ok && height + no * u > h) {
ming = pq2.top().get_weight();
pq2.pop();
//se verifica daca cea mai usoara gutuie este mai usoara decat gutuia curenta
if(ming > weight)
y = Fruit2(height, ming);
else
//daca este mai usoara-> se inlocuieste
y = Fruit2(height, weight);
pq2.push(y);
pq.pop();
}
else{
//se creste nuimarul de gutui ce trebuie culese
//creste timpul
no ++;
ok ++;
}
}
//se aduna greutatile din coada2
while (!pq2.empty()) {
greutate += pq2.top().get_weight();
pq2.pop();
}
fclose(fin);
FILE *fout = fopen("gutui.out", "w");
fprintf(fout, "%u", greutate);
fclose(fout);
//printf(">>>>>%d", greutate);
return 0;
}