Cod sursa(job #463278)

Utilizator simona.poilincaSimona Poilinca simona.poilinca Data 14 iunie 2010 21:24:29
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 3.17 kb
//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;
}