题解

问题描述

题目描述了一个数据流管理系统 Argus，它处理对数据流的查询。用户可以向 Argus 注册查询，每个查询都有一个唯一的查询 ID（Q_num）和一个返回结果的时间间隔（Period）。系统会在每个查询的指定时间间隔后返回结果，并且如果多个查询同时返回结果，它们将按照 Q_num 的升序返回。

任务是找出首先返回结果的前 K 个查询的 Q_num。

输入输出格式

• 输入：
  • 第一部分是注册查询的指令，每行一个指令，格式为 Register Q_num Period。
  • 第二部分是一个正整数 K，表示需要输出的查询数量。
  • 输入以 # 结束。
• 输出：
  • 输出前 K 个返回结果的查询的 Q_num，每行一个。

问题分析

1. 查询的注册：
   每个查询都有一个唯一的 ID（Q_num）和一个时间间隔（Period）。我们需要记录每个查询的首次返回时间。

2. 优先队列的应用：
   使用优先队列（最小堆）来管理查询的返回时间。优先队列会根据查询的返回时间排序，如果返回时间相同，则按 Q_num 升序排序。

3. 模拟查询的执行：
   每次从优先队列中取出最早返回结果的查询，输出其 Q_num，然后更新该查询的下一次返回时间，并将其重新加入优先队列。

代码解析

以下是代码的详细解析：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <queue>
using namespace std;
#define int long long
const int maxn = 100000;
char s[20];
int k;
int read()
{ 
    int x = 0, fl = 1; 
    char ch = getchar();
    while (ch < '0' || ch > '9') {  
        if (ch == '-') fl = -1; 
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {  
        x = x * 10 + (ch - '0'); 
        ch = getchar();
    }
    return x * fl;
}
struct Item {
    int q, p, t;
    bool operator<(const Item& a) const {
        if (t != a.t) return t > a.t; // 按返回时间升序
        return q > a.q; // 如果时间相同，按 Q_num 升序
    } 
} b, r;
priority_queue<Item> pq;
signed main() {
    while (true) {
        scanf("%s", s);
        if (s[0] == '#') break; // 如果输入为 "#"，结束注册
        else {
            b.q = read(); // 读取 Q_num
            b.p = read(); // 读取 Period
            b.t = b.p; // 首次返回时间
            pq.push(b); // 将查询加入优先队列
        }   	
    } 
    k = read(); // 读取 K
    while (k--) {
        r = pq.top(); // 取出最早返回结果的查询
        pq.pop();
        cout << r.q << endl; // 输出 Q_num
        r.t += r.p; // 更新下一次返回时间
        pq.push(r); // 将查询重新加入优先队列
    }
    return 0;
}

关键点解释

1. 输入处理：

   • 使用 scanf 读取指令，read 函数用于读取整数。
   • 每次读取一个指令，如果是 Register，则读取 Q_num 和 Period，并将首次返回时间设置为 Period。

2. 优先队列：

   • 使用 priority_queue 存储查询。优先队列会根据返回时间排序，如果返回时间相同，则按 Q_num 升序排序。
   • 自定义比较函数 operator<，确保优先队列按要求排序。

3. 模拟查询的执行：

   • 每次从优先队列中取出最早返回结果的查询，输出其 Q_num。
   • 更新该查询的下一次返回时间，并将其重新加入优先队列。
   • 重复上述过程 K 次。