Pagini recente » Cod sursa (job #463198) | Cod sursa (job #3230187) | Cod sursa (job #463171) | Cod sursa (job #393752) | Cod sursa (job #463696)
Cod sursa(job #463696)
//Tigora Andrei 322CA
#include<stdio.h>
#include<stdlib.h>
typedef struct {
int w;
int h;
} gutuie;
typedef struct {
int max;
int crt;
int* w;
} heap;
int compare(gutuie a,gutuie b){
/*
* Functie de comparatie intre 2 elemente de tip "gutuie".
* Elementele sunt sortate crescator dupa h, iar in caz de
* egalitate descrescator dupa w.
*/
if(a.h<b.h)
return -1;
if(a.h>b.h)
return 1;
if(a.w>b.w)
return -1;
if(a.w<b.w)
return 1;
return 0;
}
void merge_sort(gutuie *vect,int size){
/*
* MergeSort banal fara nimic deosebit... banal
*/
gutuie aux;
if(size==1)
return;
if(size==2){
if(compare(vect[0],vect[1])>0){
aux = vect[0];
vect[0] = vect[1];
vect[1] = aux;
}
return;
}
int middle = size/2,i,j,crt;
gutuie *vect1 = malloc((middle)*sizeof(gutuie));
gutuie *vect2 = malloc((size-middle)*sizeof(gutuie));
for(i=0;i<middle;i++)
vect1[i] = vect[i];
for(i=middle;i<size;i++)
vect2[i-middle] = vect[i];
merge_sort(vect1,middle);
merge_sort(vect2,size-middle);
i = 0, j = 0, crt = 0;
while(i<middle && j<size-middle)
if(compare(vect1[i],vect2[j])<=0)
vect[crt++] = vect1[i++];
else
vect[crt++] = vect2[j++];
while(i<middle)
vect[crt++] = vect1[i++];
while(j<size-middle)
vect[crt++] = vect2[j++];
free(vect1);free(vect2);
}
void remove_first(heap *choice){
/*
* Functie de eliminare a varfului heapului... neinteresant
*/
choice->crt--;
choice->w[0] = choice->w[choice->crt];
int poz = 0;
int aux;
while(1){
if(poz*2+2<choice->crt){ //are ambii fii
if(choice->w[poz*2+1]<choice->w[poz]){//primul fiu mai mic decat curentul
if(choice->w[poz*2+2]<choice->w[poz*2+1]){//al doilea mai mic decat primul
aux = choice->w[poz];
choice->w[poz] = choice->w[poz*2+2];
choice->w[poz*2+2] = aux;
poz = poz*2+2;
}
else{//primul mai mic decat al doilea
aux = choice->w[poz];
choice->w[poz] = choice->w[poz*2+1];
choice->w[poz*2+1] = aux;
poz = poz*2+1;
}
}
else{//tatal mai mare ca primul fiu
if(choice->w[poz*2+2]<choice->w[poz]){//al doilea fiu mai mic
aux = choice->w[poz];
choice->w[poz] = choice->w[poz*2+2];
choice->w[poz*2+2] = aux;
poz = poz*2+2;
}
else//ambii fii mai mari
break;
}
}
else //doar un fiu
if(poz*2+1<choice->crt){
if(choice->w[poz*2+1]<choice->w[poz]){//fiul este mai mic
aux = choice->w[poz];
choice->w[poz] = choice->w[poz*2+1];
choice->w[poz*2+1] = aux;
poz = poz*2+1;
}
else //fiul este mai mare
break;
}
else //nu are fii
break;
}
}
void add(heap *choice,int val){
/*
* Functie de adaugare in heap... ca mai sus
*/
int poz = choice->crt;
int aux;
choice->crt++;
choice->w[poz] = val;
while(poz)
if(choice->w[poz]<choice->w[(poz-1)/2]){
aux = choice->w[poz];
choice->w[poz] = choice->w[(poz-1)/2];
choice->w[(poz-1)/2] = aux;
poz = (poz-1)/2;
}
else
break;
}
int main(){
int i,crt,n;
gutuie *vect;
int high_max,low;
long long suma = 0;
heap choice;
FILE *in,*out;
in = fopen("gutui.in","r");
out = fopen("gutui.out","w");
// Citirea datelor de intrare
fscanf(in,"%d%d%d",&n,&high_max,&low);
vect = malloc(n*sizeof(gutuie));
// Se elimina gutuile care sunt mai sus decat high_max(H in enunt)
crt = 0;
for(i=0;i<n;i++){
fscanf(in,"%d%d",&vect[crt].h,&vect[crt].w);
if(vect[crt].h<=high_max){ // gutuie accesibila
crt++;
}
}
n = crt;// reactualizare n
if(crt==0){// daca nu exista gutui, rezolvarea se incheie aici
free(vect);
fclose(in);fclose(out);
fprintf(out,"%lld",suma);
return 0;
}
// Inaltimea este inlocuita cu nivelul corespunzator
for(i=0;i<n;i++)
vect[i].h = ((high_max - vect[i].h) / low) + 1;
// Sorteaza corespunzator
merge_sort(vect,n);
// Initializeaza minheapul
if(vect[n-1].h > n){
choice.w = malloc(n*sizeof(int));
choice.max = n;
}
else{
choice.w = malloc(vect[n-1].h*sizeof(int));
choice.max = vect[n-1].h;
}
choice.crt=0;
// Adauga in minheap
for(i=0;i<n;i++){
if(vect[i].h>choice.crt)//mai sunt gutui accesibile pe nivelul curent
add(&choice,vect[i].w);
else if(vect[i].w > choice.w[0]){
// gutuia curenta reprezinta o alegerea mai buna decat
// cea mai slaba alegere anterioara
remove_first(&choice);
add(&choice,vect[i].w);
}
}
// Calculul sumei
for(i=0;i<choice.crt;i++)
suma+=choice.w[i];
fprintf(out,"%lld",suma);
free(vect);free(choice.w);
fclose(in);fclose(out);
// End
return 0;
}