Pagini recente » Cod sursa (job #2303768) | Cod sursa (job #1141212) | Cod sursa (job #95307) | Cod sursa (job #2716341) | Cod sursa (job #441229)
Cod sursa(job #441229)
//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;
}