Pagini recente » Cod sursa (job #2831620) | Cod sursa (job #2276013) | Cod sursa (job #502688) | Cod sursa (job #2193012) | Cod sursa (job #463394)
Cod sursa(job #463394)
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
int N,H,U; // cu semnificatiile din enunt
typedef struct { // definirea structurii gutuie cu campurile inaltime si greutate
int h,g;
} gutuie;
gutuie *gutui; // vectorul de gutui
FILE *f,*g; // fisierele de intrare, respectiv iesire
bool comp(gutuie c1, gutuie c2) { // comparatorul pentru sortarea vectorului de gutui, descrescator dupa inaltime
return c1.h > c2.h;
return true;
}
bool compheap(int c1, int c2){ // comparatorul pentru heap : heapul folosit in algoritm va fi un minheap
return c1 > c2;
}
int main(){
int i,k,hc,j;
int max = 0;
int *heap;
f = fopen("gutui.in","r");
g = fopen("gutui.out","w");
fscanf(f,"%d %d %d\n",&N,&H,&U);
// alocari memorie
heap = (int*)calloc(N,sizeof(int));
gutui = (gutuie*)calloc(N,sizeof(gutuie));
for(i=0;i<N;i++)
fscanf(f,"%d %d\n",&gutui[i].h,&gutui[i].g);
//sortare descrescator dupa inaltime
sort(gutui,gutui+N,comp);
//se elimina gutuile care sunt la inaltimi mai mari de H
k=0;
while(gutui[k].h>H)
k++;
for(i=0;i<N-k;i++)
gutui[i]=gutui[i+k];
N=N-k; // vectorul de gutui are acum N-k gutui, presupunand ca au fost k gutui mai inalte de inaltimea H
// fac o transformare inaltimi - nivele
// toate gutuile aflate intr-o marja (h,h-U) sunt situate pe acelasi nivel
// e totuna daca iau orice gutuie de pe acest nivel pentru ridicarea crengilor
// nivelul cel mai de sus va fi nivelul 0, apoi nivelul 1, 2, etc.
// calculez nivelele pentru toate gutuile
k = 0; // nivelul curent
hc = H; // inaltimea curenta
i = 0; // contorul pentru vectorul de gutui
while(i<N){
while(gutui[i].h<=hc && gutui[i].h>(hc-U) && i<N){ // daca avem o gutuie intre hc si hc-U+1
gutui[i].h = k; // ea se afla pe nivelul k
i++;
}
hc = hc - U; // trecem la inaltimea corespunzatoare nivelului urmator
k++; // creste nivelul
}
i = 0; // nivelul pe care ne aflam in momentul de fata
k = 0; // dimensiunea heapului
for(j=0;j<N;j++){ // teta (N)
if(gutui[j].h!=i) // daca ne aflam pe un nivel mai mare
i = gutui[j].h; // se actualizeaza i
if(k<=i){ // daca mai avem loc in heap
heap[k] = gutui[j].g; // adaugam o gutuie
k++; // crestem dimensiunea heapului
push_heap(heap,heap+k,compheap); // ii actualizam proprietatea de heap - O(log k)
}
else // daca nu mai avem loc in heap
if(heap[0]<gutui[j].g){ // daca gutuia din varful heapului e mai usoara decat gutuia curenta
pop_heap(heap,heap+k,compheap); // o scoatem - O(log k)
heap[k-1] = gutui[j].g; // o inlocuim
push_heap(heap,heap+k,compheap); // actualizam proprietatea de heap - O(log k)
}
}
// Calcularea maximului
for(i=0;i<k;i++)
max = max + heap[i];
// Afisarea rezultatului
fprintf(g,"%d\n",max);
// Inchiderea fisierelor
fclose(f);
fclose(g);
return 0;
}