1284 海港 队列 模拟

标签：1284 队列 乘客 海港 int ans 国籍 数量

思路解释

 1. 数据结构选择：  

• 使用 queue 来存储每艘船的到达时间和乘客国籍信息。

 

• 使用数组 a 来记录每个国籍的乘客数量。

  2. 输入处理：  

• 读取船只数量 n。

 

• 对于每艘船，读取其到达时间 t 和乘客数量 k，然后读取每个乘客的国籍 x。

  3. 统计不同国籍的乘客数量：  

• 如果某个国籍的乘客数量为0，表示这是一个新国籍，增加不同国籍计数 ans。

 

• 将当前乘客信息加入队列 q。

  4. 移除超过24小时的船只：  

• 检查队列中的船只，如果其到达时间超过当前时间 t 的24小时（86400秒），则从队列中移除，并更新国籍乘客数量。

 5. 输出结果：  

• 对于每艘船，输出当前时间点的不同国籍乘客数量 ans。

  通过这种方法，可以高效地统计每艘船到达时的24小时内不同国籍的乘客数量。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3e5+10;

struct node {
    int t, x;
};

queue<node> q; // 用于存储船只到达时间和乘客国籍的队列
int a[N]; // 用于记录每个国籍的乘客数量
int n, k, x, t, ans; // n: 船只数量, k: 当前船的乘客数量, x: 乘客国籍, t: 当前时间, ans: 不同国籍的乘客数量
node r; // 临时变量，用于存储当前处理的船只信息

int main() {
    scanf("%d", &n); // 读取船只数量
    for (int i = 1; i <= n; i++) {
        scanf("%d %d", &r.t, &k); // 读取当前船只到达时间和乘客数量
        t = r.t; // 更新当前时间
        for (int j = 1; j <= k; j++) {
            scanf("%d", &r.x); // 读取每个乘客的国籍
            if (!a[r.x]) ans++; // 如果该国籍的乘客数量为0，表示是新国籍，增加不同国籍计数
            a[r.x]++; // 增加该国籍的乘客数量
            q.push(r); // 将当前乘客信息加入队列
        }
        r = q.front(); // 获取队列中的第一个元素
        // 移除超过24小时（86400秒）前到达的船只的乘客
        while (!q.empty() && t - r.t >= 86400) {
            q.pop(); // 移除队列中的第一个元素
            a[r.x]--; // 减少该国籍的乘客数量
            if (!a[r.x]) ans--; // 如果该国籍的乘客数量为0，减少不同国籍计数
            if (!q.empty()) r = q.front(); // 更新队列中的第一个元素
        }
        cout << ans << endl; // 输出当前时间点的不同国籍乘客数量
    }
    return 0;
}

 

标签：1284,队列,乘客,海港,int,ans,国籍,数量
From： https://www.cnblogs.com/jyssh/p/18442290