#include<iostream>
using namespace std;
typedef struct _tsk
{
	int id;
	int prd;
	int totalTime;
}TASK;
TASK tsk[1002],TMP;
int n;
bool isLeaf(int pos)
{
	return (pos>=n/2)&&(pos<n);
}
int lchild(int pos)
{
	return 2*pos+1;
}
int rchild(int pos)
{
	return 2*pos+2;
}
int parent(int pos)
{
	return (pos-1)/2;
}
bool gt(TASK a,TASK b)
{
	return ((a.totalTime>b.totalTime)||
			((a.totalTime==b.totalTime)&&(a.id>b.id)));
}
bool lt(TASK a,TASK b)
{
	return ((a.totalTime<b.totalTime)||
			((a.totalTime==b.totalTime)&&(a.id<b.id)));
}
void swap(int i,int j)
{
	TASK temp;
	temp.id=tsk[i].id;
	temp.prd=tsk[i].prd;
	temp.totalTime=tsk[i].totalTime;
	tsk[i].id=tsk[j].id;
	tsk[i].prd=tsk[j].prd;
	tsk[i].totalTime=tsk[j].totalTime;
	tsk[j].id=temp.id;
	tsk[j].prd=temp.prd;
	tsk[j].totalTime=temp.totalTime;
}
void siftdown(int pos)
{
	while(!isLeaf(pos))
	{
		int j=lchild(pos);
		int rc=rchild(pos);
		if((rc<n)&&gt(tsk[j],tsk[rc]))
			j=rc;/*set j to greater child's pos*/
		if(!gt(tsk[pos],tsk[j]))
			return;
		swap(pos,j);
	}
}
void buildMinHeap()
{
	for(int i=n/2-1;i>=0;i--)
		siftdown(i);
}
void insert(TASK task)
{
	int curr=n++;/*start at end of the heap*/
	tsk[curr].id=task.id;
	tsk[curr].prd=task.prd;
	tsk[curr].totalTime=task.totalTime;
	while((curr!=0)&&lt(tsk[curr],tsk[parent(curr)]))
	{
		swap(curr,parent(curr));
		curr=parent(curr);
	}
}
void removemin()
{
	TMP.id=tsk[0].id;
	TMP.totalTime=tsk[0].totalTime;
	TMP.prd=tsk[0].prd;
	swap(0,--n);
	if(n) siftdown(0);
}
int main()
{
	int i,query,tk=0;
	char c[9];
	while(scanf("%s",c)&&c[0]!='#'){
		scanf("%d%d",&tsk[tk].id,&tsk[tk].prd);
		tsk[tk].totalTime=tsk[tk].prd;
		tk++;
	}
	n=tk;
	buildMinHeap();
	scanf("%d",&query);
	for(i=0;i<query;i++)
	{
		removemin();
		printf("%d\n",TMP.id);
		TMP.totalTime+=TMP.prd;
		insert(TMP);
	}
	return 0;
}

• Re:原来siftdown()抄漏了一条语句!!足以致命! (0) Algor 2010-03-02 18:59:11