Pagini recente » Cod sursa (job #662627) | Cod sursa (job #1592464) | Cod sursa (job #1107121) | Cod sursa (job #66540) | Cod sursa (job #435570)
Cod sursa(job #435570)
#include <stdio.h>
#include <stdlib.h>
#include <queue>
#include <deque>
#include <vector>
#include <functional>
using namespace std;
typedef struct fruct{
int greutate;
int inaltime;
}fruct;
int compare (const void * a, const void * b) // functie de comparare folosita de qsort
{
return ( ((fruct*)a)->inaltime - ((fruct*)b)->inaltime );
}
int main(){
FILE* f,*g;
f = fopen("gutui.in","rt");
g = fopen("gutui.out","wt");
int n,h,u;
int height;
int i;
int niv_curent;
fruct* v;
v = (fruct*)malloc(100000*sizeof(fruct));
fscanf(f,"%d%d%d",&n,&h,&u);
for(i = 0; i < n; i++){
fscanf(f,"%d%d\n",&height,&v[i].greutate);
v[i].inaltime=(h-height)/u; // inaltimea reprezinta nivelul pe
// care se afla fructul curent.
// pe nivelul 0 se afla fructele cele mai
// departate de Gigel. Acestea nu pot
// fi culese decat la primul pas. Fructele
// de pe nivelul 1 pot fi culese in primii
// 2 pasi, s.a.m.d.
}
qsort (v, n, sizeof(fruct), compare); // sortam fructele in functie de inaltime
priority_queue < int, vector<int>, greater<int> > minheap;
i=0;
while(i<n){
niv_curent=v[i].inaltime;
while((niv_curent==v[i].inaltime)&&(i<n)){ // inseram toate fructele de pe
// nivelul curent in coada de prioritati
minheap.push(v[i].greutate);
i++;
}
while((int)minheap.size()>niv_curent+1){
minheap.pop(); // scoatem din coada cele mai mici elemente
// astfel incat pentru pasul urmator (k) sa avem
// in coada de prioritati maxim k-1 elemente
}
}
// la sfarsitul ciclului vom avea in coada de prioritati exact greutatile
// fructelor ce trebuiesc culese de Gigel.
unsigned int s=0;
while((int)minheap.size()>0){
s+=(int)minheap.top(); // facem suma greutatilor
minheap.pop();
}
fprintf(g,"%d",s);
fclose(f);
fclose(g);
}