海港

题目 海港

思路分析

滑动窗口维护一天（86400秒）内的船只

很容易想到用一个数组维护各国籍的人数 减少就-- 减没了 就整个种数--

可以直接用个队列维护所有的人 记录一个他到达的时间 和 国籍

因为这个数据量会比较大 所以可以把队列做成循环的 若用到N位置处 就回到0处用

代码实现

#include <bits/stdc++.h>

using namespace std;

const int N = 300010; // 设定一个足够大的数，用于存储所有可能的乘客信息

// 循环队列维护每个人q[i][0]保存时刻，q[i][1]保存国籍

int q[N][2];

// 每个国籍的人数计数器

LL cnt[N];

int main()

{

    int n;

    scanf("%d", &n);

    // hh 和 tt 分别表示循环队列的头和尾（tt指向队尾元素的下一个位置）

    int hh = 0, tt = 0;

    // 用于记录不同国籍的数量

    int ans = 0;

    while(n --)

    {

        int t, k;

        scanf("%d%d", &t, &k);

        // 移除超过24小时的船只信息

        while(hh != tt && t - q[hh][0] >= 86400)

        {

            int nation = q[hh][1];

            cnt[nation]--;

            // 如果某个国籍的人数减到0，则减少不同国籍的数量

            if(cnt[nation] == 0)

                ans--;

            hh++;

            if(hh == N) hh = 0; // 循环回到数组开始位置

        }

        // 添加新船只的乘客国籍信息

        for(int i = 1; i <= k; i ++)

        {

            int x;

            scanf("%d", &x);

            // 如果是新的国籍，则增加不同国籍的数量

            if(cnt[x] == 0)

                ans++;

            cnt[x]++;

            // 将船只信息添加到队列中

            q[tt][0] = t, q[tt][1] = x;

            tt++;

            if(tt == N)

                tt = 0; // 循环回到数组开始位置

        }

        cout << ans << endl;

    }

    return 0;

}

同类题型

视频讲解

⬅️ 机器翻译 🏠 00-刷题理模型 ➡️ 蚯蚓