Pagini recente » Cod sursa (job #2169444) | Cod sursa (job #1358843) | Cod sursa (job #223632) | Cod sursa (job #65818) | Cod sursa (job #463543)
Cod sursa(job #463543)
#include<stdio.h>
#include<list>
#include<stdlib.h>
#include<algorithm>
#include<vector>
using namespace std;
FILE* fin;
FILE* fout;
typedef struct gut{
unsigned int greutate;
unsigned int tmp;
}*gutui;
// functie comparator pentru sortare qsort cu functia din clasa list
bool compare_desc(gut first,gut second)
{
if (first.tmp < second.tmp ) return true;
else
if(first.tmp == second.tmp)
{ if(first.greutate<=second.greutate)
return true;
else
return false;
}
return false;
}
// comparator ce ajuta la crearea min_heap
bool heap_min(unsigned int first,unsigned int second)
{
if ( first > second ) return true;
return false;
}
int main(){
unsigned int h,u,a,g;
unsigned int suma=0;
unsigned int v[]={0};
unsigned int n,i,max;
int t;
fin=fopen("gutui.in","r");
fout=fopen("gutui.out","w");
list<gut> cos;
list<gut>::iterator it;
fscanf(fin,"%d %d %d\n",&n,&h,&u);
gut *aux;
if(h%u==0)
{
t=0;
max=h/u;
}else
{max=h/u+1;
t=1;
}
for(i=0;i<n;i++)
{
aux=(gut*)malloc(sizeof(struct gut));
fscanf(fin,"%u %u\n",&a,&g);
// obtinerea momentului de timp maxim in care se poate culege gutuia
if(a+(max-t-(a/u))*u<=h)
aux->tmp=max-t-(a/u-1);
else
aux->tmp=max-t-(a/u);
aux->greutate=g;
cos.push_back(*aux);
free(aux);
}
cos.sort(compare_desc);
unsigned int *matrice;
matrice=(unsigned int*)calloc(max+1,sizeof(unsigned int));
unsigned int nivel=0;
int ind=0;
unsigned int top,poz;
it=cos.begin();
ind=it->tmp;
poz=it->tmp;
top=it->tmp;
nivel=0;
// creare heap;
vector<unsigned int> luate(v,v+0);
make_heap(luate.begin(),luate.end(),heap_min);
for(i=1;i<=n;i++)
{
if(nivel<it->tmp){
// se insereaza valoarea in heap
suma=suma+it->greutate;
luate.push_back(it->greutate);
push_heap(luate.begin(),luate.end(),heap_min);
nivel++;
}
else
{if(luate.front()<it->greutate)
//nivelul este mai mare sau egal cu momentul de timp al gutuii respective, se verifica daca nu
//cumva luand acesta gutuie obtinem o grutate mai mare, adica cautam minimul si il inlocuim cu greutatea gutuii respective (daca acesta este mai mic)
// se scoate valoarea mica din heap si din suma si se inlocuieste cu noua greutate
suma=suma-luate.front()+it->greutate;
pop_heap(luate.begin(),luate.end(),heap_min);
luate.pop_back();
luate.push_back(it->greutate);
push_heap(luate.begin(),luate.end(),heap_min);
}
it++;
}
fprintf(fout,"%u",suma);
free(matrice);
fclose(fin);
fclose(fout);
return 0;
}