Pagini recente » Cod sursa (job #2126468) | Istoria paginii runda/oni2012_9_1/clasament | Cod sursa (job #2839140) | Cod sursa (job #999068) | Cod sursa (job #441305)
Cod sursa(job #441305)
#include <stdlib.h>
#include <stdio.h>
#define CHILD(node) ((node) * 2 + 1)
typedef struct gutuie{
int interval;
int g;
}gutuie;
//pentru transformarea priority_queue in minheap
/*class mycomparison{
public:
bool operator() (const int& a, const int& b) const{
return (a > b);
}
};*/
//pentru qsort
int sortare(const void * x,const void * y){
gutuie *temp1=(gutuie*)x;
gutuie *temp2=(gutuie*)y;
return ( temp1->interval - temp2->interval );
};
static void heapify( int a[], int i, int n ){
while ( CHILD( i ) < n ) {
int child = CHILD( i );
if ( child + 1 < n && a[child] > a[child + 1] )
++child;
if ( a[i] > a[child] ) {
int temp = a[i];
a[i] = a[child];
a[child] = temp;
}
++i;
}
}
void make_heap( int a[], int n ){
int i = n / 2;
while ( i-- > 0 )
heapify( a, i, n );
}
void pop_heap( int heap[], int n ){
int temp = heap[0];
heap[0] = heap[n];
heap[n] = temp;
heapify( heap, 0, n-1 );
}
int main( void ){
int heap[110000];
int dim=0;
/*
for ( i = 0; i < 11; i++ )
heap[i] = rand() % 100;
make_heap( heap, 11 );
for ( n = 10; n >= 0; n-- ) {
printf( "%d ", heap[0] );
pop_heap( heap, n );
}*/
int n,h,u;
int inaltime;
int i,rang,max = 0;
gutuie v[110000];
FILE *in=fopen("gutui.in","rt");
FILE *out=fopen("gutui.out","wt");
fscanf(in,"%d %d %d",&n,&h,&u);
//priority_queue<int,vector<int>,mycomparison> minheap;
for (i = 0;i < n;i++){
fscanf(in,"%d %d",&inaltime,&v[i].g);
v[i].interval = (h - inaltime) / u;
}
for (i = 0;i < n;i++)
if (v[i].interval >= 0)
v[i].interval++;
qsort(v,n,sizeof(gutuie),sortare);
int j;
i=0;
//pozitionare pe prima gutuie disponibila (interval pozitiv)
while(v[i].interval < 0)
i++;
rang = v[i].interval;
while (i < n){
if (v[i].interval == rang){
dim++;
heap[dim-1]=v[i].g;
make_heap(heap,dim);
i++;
for (j=0;j<dim;j++)
printf("p=%d ",heap[j]);
printf("\n");
printf("dim=%d g=%d\n",dim,v[i].g);
}
else {
while(dim > rang) {
printf("pop=%d\n",heap[0]);
pop_heap(heap,dim);
dim--;
for (j=0;j<dim;j++)
printf("h=%d ",heap[j]);
printf("\n");
}
rang=v[i].interval;
}
for (j=0;j<dim;j++)
printf("%d ",heap[j]);
printf("\n");
}
while(dim > rang) {
pop_heap(heap,dim);
dim--;
}
for (j=0;j<dim;j++){
max = max + heap[j];
}
fprintf(out,"%d",max);
return 0;
}