Pagini recente » Cod sursa (job #967824) | Cod sursa (job #3177197) | Cod sursa (job #150026) | Cod sursa (job #1989697) | Cod sursa (job #463588)
Cod sursa(job #463588)
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
typedef struct {
int greutate;
int inaltime;
} gutuie;
//interschimba 2 elemente din vectorul de gutui
void swap(gutuie *a, gutuie *b) {
gutuie aux;
aux=*a;
*a=*b;
*b=aux;
}
//auxiliar pentru functia de sortare quicksort
int choose_pivot(int i, int j) {
return ((i+j)/2);
}
//sorteaza descrescator in functie de greutate in vectorul de gutui
void qsort(gutuie *g, int m, int n) {
int key,i,j,k;
if (m<n)
{
k=choose_pivot(m,n);
swap(&g[m],&g[k]);
key=g[m].inaltime;
i=m+1;
j=n;
while (i<=j)
{
while ((i<=n)&&(g[i].inaltime>=key))
i++;
while ((j>=m) &&(g[j].inaltime<key))
j--;
if (i<j)
swap(&g[i],&g[j]);
}
swap(&g[m],&g[j]);
qsort(g,m,j-1);
qsort(g,j+1,n);
}
}
//comparator util pentru pop_heap si push_heap, reprezentand functia de pozitionare a unei gutui in heap
bool comparatorGreutate(gutuie a, gutuie b) {
return (a.greutate>b.greutate);
}
int main() {
//DECLARARI VARIABILE
int n,h,u,i,gt=0;
FILE *in=fopen("gutui.in","r");
FILE *out=fopen("gutui.out","w");
vector<gutuie> heap;
fscanf(in,"%u%u%u",&n,&h,&u);
//ALOCARE DE MEMORIE
gutuie *g=(gutuie*)malloc(n*sizeof(gutuie));
//CITIRE DIN FISIER INTRARE SI INITIALIZARE ARRAY de gutui g
for (i=0;i<n;i++)
fscanf(in,"%u%u",&g[i].inaltime,&g[i].greutate);
//sortare vector de gutui dupa inaltime
qsort(g,0,n-1);
//adaugare prima gutuie
heap.push_back(g[0]);
for (i=1;i<n;i++) {
//daca nu mai pot fi adaugate elemente in heap si gasim o gutuie cu o greutate mai mare decat varful heap-ului
if (heap.size()==(1+(h-g[i].inaltime)/u) && heap.front().greutate<g[i].greutate) {
//extrage ultimul element al heap-ului, considerat a fi reprezentat de gutuia cu cea mai mica greutate
pop_heap(heap.begin(),heap.end(),comparatorGreutate);
heap.pop_back();
//adauga noua gutuie cu greutatea mai mare decat varful heap-ului
heap.push_back(g[i]);
push_heap(heap.begin(),heap.end(),comparatorGreutate);
}
//daca inca se mai pot adauga gutui in heap
else if (heap.size()!=(1+(h-g[i].inaltime)/u)) {
//adauga gutuia i si reface structura heap-ului
heap.push_back(g[i]);
push_heap(heap.begin(),heap.end(),comparatorGreutate);
}
}
//calculam greutatile gutuilor ramase in heap
for (i=0;i<heap.size();i++)
gt+=heap[i].greutate;
//AFISAREA REZULTATULUI IN FISIERUL DE IESIRE
fprintf(out,"%u\n",gt);
//ELIBERARE MEMORIE
free(g);
//INCHIDERE FISIERE INTRARE/IESIRE
fclose(in);
fclose(out);
return 0;
}