Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 只是想练习最小堆……（貌似优先队列和堆都是32ms）

Posted by YanXB at 2015-01-25 11:37:29 on Problem 2051 and last updated at 2015-01-25 11:37:35
In Reply To:不明白不用STL的是什么心态（附代码） Posted by:jordandandan at 2013-08-21 09:42:54
```#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct _heap
{
int array[1002][3],size;
}heap;
void build(heap *h);
void maintain(heap *h,int index);
int getcmp(heap *h,int m,int n);
void getswap(heap *h,int m,int n);
int main(int argc,char *argv[])
{
heap h;
memset(h.array,0,sizeof(h.array));
h.size=0;
while(1)
{
char com[12]={0};
int num,period;
scanf("%s%*c",com);
if(strcmp(com,"#")==0)
break;
scanf("%d%*c%d%*c",&num,&period);
h.array[h.size+1][0]=num;
h.array[h.size+1][1]=period;
h.array[h.size+1][2]=1;
h.size++;
}
build(&h);
int n;
scanf("%d",&n);
while(n--)
{
printf("%d\n",h.array[1][0]);
h.array[1][2]++;
maintain(&h,1);
}
return (0);
}
void build(heap *h)
{
int i;
for(i=h->size/2;i>0;i--)
maintain(h,i);
}
void maintain(heap *h,int index)
{
int min;
if(index*2<=h->size&&getcmp(h,index*2,index)==1)
min=index*2;
else
min=index;
if(index*2+1<=h->size&&getcmp(h,index*2+1,min)==1)
min=index*2+1;
if(min!=index)
{
getswap(h,index,min);
maintain(h,min);
}
}
int getcmp(heap *h,int m,int n)
{
if(h->array[m][1]*h->array[m][2]<h->array[n][1]*h->array[n][2])
return (1);
else if(h->array[m][1]*h->array[m][2]>h->array[n][1]*h->array[n][2])
return (0);
else
{
if(h->array[m][0]<h->array[n][0])
return (1);
return (0);
}
}
void getswap(heap *h,int m,int n)
{
int tp[3];
tp[0]=h->array[m][0];
tp[1]=h->array[m][1];
tp[2]=h->array[m][2];
h->array[m][0]=h->array[n][0];
h->array[m][1]=h->array[n][1];
h->array[m][2]=h->array[n][2];
h->array[n][0]=tp[0];
h->array[n][1]=tp[1];
h->array[n][2]=tp[2];
}
```

Followed by: