POJ2051【最小优先级队列】【堆实现】

by Charlie on Jul.19, 2008, under ACM Life, Hits 473

题目描述：
Argus
Time Limit: 1000MS Memory Limit: 30000K
Total Submissions: 4468 Accepted: 1916

Description
A data stream is a real-time, continuous, ordered sequence of items. Some examples include sensor data, Internet traffic, financial tickers, on-line auctions, and transaction logs such as Web usage logs and telephone call records. Likewise, queries over streams run continuously over a period of time and incrementally return new results as new data arrives. For example, a temperature detection system of a factory warehouse may run queries like the following.

Query-1: “Every five minutes, retrieve the maximum temperature over the past five minutes.”
Query-2: “Return the average temperature measured on each floor over the past 10 minutes.”

We have developed a Data Stream Management System called Argus, which processes the queries over the data streams. Users can register queries to the Argus. Argus will keep the queries running over the changing data and return the results to the corresponding user with the desired frequency.

For the Argus, we use the following instruction to register a query:

Q_num (0 < Q_num <= 3000) is query ID-number, and Period (0 < Period <= 3000) is the interval between two consecutive returns of the result. After Period seconds of register, the result will be returned for the first time, and after that, the result will be returned every Period seconds.

Here we have several different queries registered in Argus at once. It is confirmed that all the queries have different Q_num. Your task is to tell the first K queries to return the results. If two or more queries are to return the results at the same time, they will return the results one by one in the ascending order of Q_num.

Input
The first part of the input are the register instructions to Argus, one instruction per line. You can assume the number of the instructions will not exceed 1000, and all these instructions are executed at the same time. This part is ended with a line of “#”.

The second part is your task. This part contains only one line, which is one positive integer K (<= 10000).

Output
You should output the Q_num of the first K queries to return the results, one number per line.

Sample Input

Sample Output

2004
2005
2004
2004
2005

题目大意：

给出任务的id（各个任务唯一）和执行间隔（各个任务不唯一）；要求按照执行的时间顺序来输出要求的钱几个任务id号；当两个任务在同一个时间执行时，先输出id小的；

解题思路：

显然是要求按照执行的时间先后顺序来输出结果；首先考虑排序，发现排序的话，根本不能确定每个任务执行多少次能满足题目要求，所以肯定是不可行的；既然要求按照时间的先后顺序来输出，那么可以构造优先队列，每次取队头，然后再根据取出任务的执行情况将下一次的执行时间插入到队列里；直到取出满足要求的个数任务为止。

数据范围：

任务的id号：0—3000；任务时间间隔：0—3000；要求的输出个数：<10000；任务个数： <1000;

边界数据：

基本没有；

ac代码；

#include “stdio.h”
#include “iostream”
using namespace std;
typedef struct _node
{
int id;
int key;
}Node;
Node team[10001] = {0};
int mul[3001];
int totalwant = 0;
int heapsize1 = 0;
//many keywords to sort using qsort~~~
int compare(void const *a, void const *b)
{
if (((Node *)a)->key == ((Node *)b)->key) return 0;
return ((Node *)a)->key > ((Node *)b)->key?1:-1;
}
void increase(int i)
{
int parent = 0;
Node tmp;
parent = i/2;
if ((parent >= 1)&&((team.key < team[parent].key)||(team.key == team[parent].key&&team.id < team[parent].id)))
{
tmp.id = team.id;
tmp.key = team.key;
///
team.id = team[parent].id;
team.key = team[parent].key;
///
team[parent].id = tmp.id;
team[parent].key = tmp.key;
increase(parent);
}
}
void intoheap(int idx, int keyx)
{
heapsize1++;
team[0].key++;
team[heapsize1].id = idx;
team[heapsize1].key = keyx;
increase(heapsize1);
}
void adjust(int i)
{
int l, r, most;
Node tmp;
l = i*2;
r = l + 1;
if ((l <= team[0].key)&&((team[l].key < team.key)||(team[l].key == team.key&&team[l].id < team.id)))
{
most = l;
}
else
{
most = i;
}
if ((r <= team[0].key)&&((team[r].key < team[most].key)||(team[r].key == team[most].key&&team[r].id < team[most].id)))
{
most = r;
}
if (most != i)
{
tmp.id = team[most].id;
tmp.key = team[most].key;
///
team[most].id = team.id;
team[most].key = team.key;
///
team.id = tmp.id;
team.key = tmp.key;
adjust(most);
}
}
void makeheap()
{
for (int i = heapsize1/2; i >= 1; –i)
{
adjust(i);
}
}
Node gettop()
{
Node t;
printf(”%d\n”, team[1].id);
t.id = team[1].id;
t.key = team[1].key;
team[1].id = team[heapsize1].id;
team[1].key = team[heapsize1].key;
heapsize1–;
team[0].key–;
adjust(1);
return t;
}
int main()
{
freopen(”e:\\in.txt”, “r”, stdin);
char temp[10];
int id, key;
int index = 0;
Node getid;
int kk;
for (int i = 0; i < 3001; ++i)
mul = 1;
while(scanf(”%s”, temp))
{
if (temp[0] == ‘#’) break;
index++;
scanf(”%d%d”, &team[index].id, &team[index].key);
}
team[0].key = index;
heapsize1 = index;
scanf(”%d”, &totalwant);
//input the heap members~~~~ and ~~~~~how many they want to output~~~~
//qsort(team, (size_t)index, sizeof(Node), compare);
makeheap();
while(totalwant–)
{
getid = gettop();
kk = mul[getid.id];
mul[getid.id]++;
intoheap(getid.id, (getid.key/kk)*mul[getid.id]);
}
return 0;
}
【可优化】