Cod sursa(job #441229)

Utilizator angel_pacPetre Andreea Cristina angel_pac Data 12 aprilie 2010 20:29:48
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 1.96 kb
//Petre Andreea Cristina 321 CA Tema 1 PA

#include <stdio.h>
#include <stdlib.h>
#include <queue>

using namespace std;
//clasa de gutui
class gutui_t {
	public:
		int h;	//inaltime
		int g;	//greutate
	public:
		//constructori
		gutui_t(int hval, int gval);
		gutui_t(){
			h = 0;
			g = 0;
		}
		~gutui_t(){}
		//comparator pt priority queue
		bool operator<(const gutui_t&) const;   
}; 
gutui_t::gutui_t (int hval, int gval){
	h = hval;
	g = gval;
}
//comparator pt priority queue
bool gutui_t::operator<(const gutui_t& snd) const
{
  return g > snd.g;
}
//comaprator pt quick sort
int comp( const void* x, const void* y){
		gutui_t fst = *(gutui_t*)x;
		gutui_t snd = *(gutui_t*)y;
		return snd.h - fst.h; 
}
int main(){
	FILE *f, *out;
	int n, hmax, u, i, first = 1, level = 1, val = 0;
	gutui_t gutuie;
	//deschid fisiere
	f = fopen("gutui.in", "r");
	out= fopen("gutui.out", "w");
	//citire
	fscanf(f,"%d %d %d\n",&n, &hmax, &u);
	gutui_t *v = (gutui_t *)calloc(n, sizeof(gutui_t));
	priority_queue <gutui_t> pq;
	
	//citire
	for (i = 0 ; i < n ;i ++){
		fscanf(f, "%d %d\n", &gutuie.h, &gutuie.g);
		if( gutuie.h <= hmax){
			//gutuie.l = (hmax - gutuie.h) / u   + 1;
			v[i] = gutuie;
		}
	}
	
 	//ordonare dupa greutate..O(nlogn)
	qsort(v, n, sizeof(gutui_t), comp);
	
	//pentru fiecare gutuie
	for(i = 0 ; i < n ;){
		if( ( v[i].h + level * u) > hmax && first > 0 ){	//verific daca va disparea la nivelul urmator; daca e prima din nivel o bag in coada
			pq.push(v[i]); //O(log n)
			first --;
			i++;
		}
		else if( !first && (v[i].h + level * u) > hmax ){ //daca nu e prima scot minimul din coada si bag maximul
			gutuie = pq.top();
			
			if(v[i].g > gutuie.g){
				pq.pop();//O(log(n))
				pq.push(v[i]);//O(log(n))
			}
		
			i++;
			
		}
		else{
			level++;		//cresc nivelul ....O(m) < O(n log n)
			first++;
		}
	}
	//fac suma...maxim O(nlog(n))
	while(!pq.empty()){
		gutuie = pq.top();
		val+=gutuie.g;
		pq.pop();
	}
	
	fprintf(out, "%d", val);
	fclose(f);
	fclose(out);
	
	return 0;
}