#include<stdio.h>
#define MAX 200000
struct node
{
    int fval;
    int num;
    int lval;
}a[MAX];
int pos;
void insert(int qnum,int first_val,int current_val)
{
     int i=pos;
     while(i>=2 && a[i/2].lval>=current_val )
     {
       if(a[i/2].lval==current_val)
       {
          if(a[i/2].num>qnum)
          {
             a[i].fval=a[i/2].fval;
             a[i].lval=a[i/2].lval;
             a[i].num=a[i/2].num;
          }
       }
       else {
                  
            a[i].fval=a[i/2].fval;
            a[i].lval=a[i/2].lval;
            a[i].num=a[i/2].num;
            }
           i=i/2;  
     }        
            
             a[i].fval=first_val;
             a[i].num=qnum;
             a[i].lval=current_val;//printf("%d ",a[i].lval);
             pos++;
    
}
int deletemin()
{
    int min=a[1].num;
    int ll_num=a[1].num;
    int ll_fval=a[1].fval;
    int ll_lval=a[1].lval;
    int l_num=a[pos-1].num;
    int l_fval=a[pos-1].fval;
    int l_lval=a[pos-1].lval;
    int i;
    int child;
    for(i=1;i*2<pos;i=child)
    {
         child=2*i;
        if(a[child+1].lval==a[child].lval  &&(child+1!=pos) )
        {
           if(a[child+1].num<a[child].num)
           child++;
        }   
        else if(a[child+1].lval<a[child].lval  &&(child+1!=pos))
        child++;
       if(l_lval<a[child].lval)
       break;
           else   {
                 a[i].lval=a[child].lval;
                 a[i].fval=a[child].fval;
                 a[i].num=a[child].num;
                  }  
                 

   }
    a[i].lval=l_lval;
    a[i].fval=l_fval;
    a[i].num=l_num;
    pos--;
    insert(ll_num,ll_fval,ll_fval+ll_lval);
    return min;
}

int main()
{
    freopen("in.txt","r",stdin);
    pos=1;
    char b[100];
    int qnu,va;
    while( scanf("%s",b) && b[0]!='#')
    {
           scanf("%d %d",&qnu,&va);
           insert(qnu,va,va);
    }
    int k;
    scanf("%d",&k);
    int num=0;
    int i;
    
    while(num<k)
    {
      printf("%d\n",deletemin());
      //for(i=1;i<=2;i++)
      //printf("tt%d %d %dtt",a[i].num,a[i].fval,a[i].lval);
     num++;
    }
    while(1);
    return 0;
}  
        

• Re:哪位大牛帮忙看下我的对哪有问题啊？ (2475) snowbirds 2009-05-13 17:13:21