Pagini recente » Cod sursa (job #1004608) | Cod sursa (job #2346943) | Cod sursa (job #974035) | Cod sursa (job #1550694) | Cod sursa (job #437561)
Cod sursa(job #437561)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define NMAX 100001
typedef struct {
unsigned int ht;
unsigned int g;
unsigned int ns;
}elem;
int comp(const void *a, const void *b){
elem *p1 = (elem*)a;
elem *p2 = (elem*)b;
if (p1->ns < p2->ns)
return 1;
if (p1->ns > p2->ns)
return -1;
return 0;
}
void upHeap(elem heap[], int m){
elem aux;
if (m == 1)
return;
if (heap[m/2].g < heap[m].g){
aux = heap[m/2];
heap[m/2] = heap[m];
heap[m] = aux;
upHeap(heap, m/2);
}
}
void eliminaHeap(elem heap[], int* size){
elem aux;
int i,next;
heap[1] = heap[*size];
next = 1;
(*size)--;
do{
i = next;
if (2*i <= *size){
if (heap[i].g < heap[2*i].g)
next = 2*i;
else
next = i;
}
if (2*i+1 <= *size)
if (heap[next].g < heap[2*i+1].g)
next = 2*i+1;
if (next != i){
aux = heap[next];
heap[next] = heap[i];
heap[i] = aux;
}
}
while (next != i);
}
int main(){
unsigned int n,h,u;
int i, j;
elem *gutui, *p;
elem heap[NMAX];
int size;
int g = 0;
FILE *fin = fopen("gutui.in", "r");
fscanf(fin,"%d %d %d",&n,&h,&u);
gutui = (elem*)malloc(n * sizeof(elem));
for (p = gutui, i = 0; i < n; i++, p++){
fscanf(fin,"%d %d", &(p->ht), &(p->g));
p->ns = (h - p->ht) / u + 1;
}
fclose(fin);
qsort(gutui, n, sizeof(elem),comp);
for (p = gutui, j = 0, i = gutui->ns; i >= 1; i--){
while (p->ns == i && j < n){
size++;
heap[size] = *p;
upHeap(heap, size);
p++;
j++;
}
if (size != 0){
g += heap[1].g;
eliminaHeap(heap,&size);
}
}
FILE *fout = fopen("gutui.out", "w");
fprintf(fout, "%d\n", g);
fclose(fout);
return 0;
}