最小堆的维护，POJ(2051)

题目链接：http://poj.org/problem?id=2051

///维持最小堆(优先队列)POJ2051

#include <iostream>

#include <string>

using namespace std;

struct Node {

    int Now;    ///出堆的时间

    int id;

    int p;  ///时间间隔

};

Node node [];

int K;  ///输出个数

void down (Node H[],int s,int m) {

    ///向下调整，s是要调整的编号，m是堆的size

    Node rc=H[s];

    for(int j=s*; j<=m; j*=) {

        if(j<m) {

            if(H[j].Now>H[j+].Now) {   ///两个子节点中找到那个较小者

                j++;

            } else {

                ///如果相等，比较ID

                if(H[j].Now==H[j+].Now&&(H[j].id>H[j+].id))

                    j++;

            }

        }

        if(rc.Now<H[j].Now||(rc.Now==H[j].Now&&rc.id<H[j].id))

            break;

        H[s]=H[j];  ///更新子节点

        s=j;

    }

    H[s]=rc;    ///最后交换的子节点换上rc

}

///建立一个最小堆

void MakeMinHeap(Node H[],int length) {

    for(int i=length/; i>; --i)

        down(H,i,length);

}

int main() {

    string str;

    int i=;

    cin>>str;

    while(str.compare("#")!=) {

        cin>>node[i].id>>node[i].p;

        node[i].Now=node[i].p;

        i++;

        cin>>str;

    }

    int len=i-;

    cin>>K;

    MakeMinHeap(node,len);

    for(int i=; i<=K; i++) {

        cout<<node[].id<<endl;

        node[].Now+=node[].p;

        down(node,,len);   ///修改顶点后再次调整最小堆

    }

    return ;

}