最小堆解决Argus POJ 2051

题目链接

POJ 2051

题目描述(Description)

Argus

Argus是一个数据流管理系统，可以在数据流上处理多个query。Argus接收的查询指令格式如下：

Register Q_num Period

Q_num (0 < Q_num <= 3000)是查询ID号码，Period（0<period<=300)是两个查询结果之间的时间间隔。一旦一个ID号码被注册，查询结果会在period时间之后返回，以后每隔Period返回一次结果。

我们有很多不同的查询在同一时间注册，所有的查询都有一个不同的ID号。你的任务是求出前K个查询的Q_num。

输入样例：

Register 2004 200
Register 2005 300
#
5

输出样例：

2004
2005
2004
2004
2005

分析(Analysis)

1. 建立一个struct，包含当前时间，query num，period；

2. 建立一个最小堆BuildHeap()，每次返回堆顶元素，然后对最小堆向下做调整down()。

代码

#include<iostream>
#include<string>

using namespace std;

struct Node{
    int Cur;          //当前时间
    int Q_num;         //query id
    int period;      //时间间隔 
};

Node node[3000];

void down(Node heap[],int s,int size)
{
    Node c=heap[s];
    int q=2*s;
    while(q<=size){
        if(q<size)//先比较左右子结点 
        {
            if(heap[q].Cur>heap[q+1].Cur)//选择当前时间小的子节点 
                q++;
            else if((heap[q].Cur==heap[q+1].Cur)&&(heap[q].Q_num>heap[q+1].Q_num))
            //两个当前时间相同，则输出ID号较小的子节点
                q++;
        }
        //再比较根节点与左右子节点 
        if(heap[q].Cur>c.Cur||((heap[q].Cur==c.Cur)&&(heap[q].Q_num>c.Q_num)))
            break;
        else
            heap[s]=heap[q];
            s=q;
            q=2*s;
    }
    heap[s]=c;
} 

void BuildHeap(Node heap[],int size)
{
    for(int i=size/2;i>0;--i)//插入非终端结点 
        down(heap,i,size);
}

int main()
{
    string str;
    cin>>str;
    int i=0;
    while(str.compare("#")!=0){
        i++;
        cin>>node[i].Q_num>>node[i].period;
        node[i].Cur=node[i].period;
        cin>>str;
    }
    int k;
    cin>>k;
    BuildHeap(node,i);
    for(int j=1;j<=k;j++){
        cout<<node[1].Q_num<<endl;//把堆顶元素输出
        node[1].Cur+=node[1].period;//当前时间加上时间间隔 
        down(node,1,i);//向下调整堆
    }
    return 0;
}