http://acm.hdu.edu.cn/showproblem.php?pid=1509
#include<stdio.h>
struct Heap{
int para;
int pri;
int c;
char name[20];
}hh[901];
void Putheap(Heap *a,int i)
{
Heap b;
while(i>1 && a[i].pri < a[i>>1].pri)
{
b = a[i];
a[i] = a[i>>1];
a[i>>1] =b;
i >>= 1;
}
}
void Getheap(Heap *a,int max)
{
if(max==0)
return ;
Heap b;
a[0] = a[1];
a[1] = a[max];
int i = 1;
int j = 2;
while(j<max)
{
if(j<max-1 && (a[j].pri>a[j+1].pri || a[j].pri==a[j+1].pri && a[j].c>a[j+1].c))
j++;
if(a[i].pri>a[j].pri || a[i].pri==a[j].pri && a[i].c>a[j].c)
{
b = a[i];
a[i] = a[j];
a[j] = b;
i = j;
j = i<<1;
}
else
break;
}
}
int main()
{
int k=1,cnt=0;
char com[10];
while (scanf("%s",com)==1)
{
cnt ++;
if(com[0]=='G')
{
hh[0].name[0] = 0;
Getheap(hh,k-1);
if(hh[0].name[0])
{
k--;
printf("%s %d\n",hh[0].name,hh[0].para);
}
else
puts("EMPTY QUEUE!");
}
else
{
hh[0].pri = 0x80000000;
scanf("%s%d%d",hh[k].name,&hh[k].para,&hh[k].pri);
hh[k].c = cnt;
Putheap(hh,k);
k ++;
}
}
return 0;
}
寫了好久。。。主要是沒有考慮如果相同，先進的先出，看了別人的優先隊列的程序才知道。。
posted on 2009-02-24 20:10
shǎ崽 閱讀(267)
評論(2) 編輯 收藏 引用