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

## 建堆代码是抄书的，为什么还是错？难道教材错了？进来看看

Posted by Algor at 2010-03-02 00:27:44 on Problem 2051
```#include<iostream>
using namespace std;
typedef struct _tsk
{
int id;
int prd;
int totalTime;
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;
}
{
return ((a.totalTime>b.totalTime)||
((a.totalTime==b.totalTime)&&(a.id>b.id)));
}
{
return ((a.totalTime<b.totalTime)||
((a.totalTime==b.totalTime)&&(a.id<b.id)));
}
void swap(int i,int j)
{
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);
}
{
int curr=n++;/*start at end of the heap*/
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;
}```

Followed by: