P2058. 海港

发表于 分类于 阅读次数： Waline： 本文字数： 531 阅读时长 ≈ 2 分钟

考点

  • 队列
  • 滑动窗口
  • 模拟

题解

见思路

思路

标准的队列模板题，或者说滑动窗口模板题

一个区间有序，要让区间和保证小于等于某值，很显然可以用以下步骤达成：

  1. 初始时，左指针l和右指针r同在一个位置
  2. 当左右指针构成的区间和满足要求时，右指针r一直向右移
  3. 若不满足要求，则左指针l向右移，缩短区间长度，直到满足条件或两指针再次重合

朴素版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <bits/stdc++.h>
using namespace std;
const int LEN = 1e5 + 10;
//记录各国籍的人数
unordered_map<int, int> mp;
struct Node
{
    int t_;//船到达时间
    int k_;//人数
    vector<int> v_;//存放该船的乘客
} arr[LEN];

#define rt arr[r].t_
#define rk arr[r].k_
#define rv arr[r].v_
#define lt arr[l].t_
#define lk arr[l].k_
#define lv arr[l].v_

int main()
{
    int n, in, l = 0, r = 0;//区间的左右指针
    cin >> n;
    while (n--)
    {
        cin >> rt >> rk;
        for (int i = 0; i < rk; ++i)
        {
            cin >> in;
            rv.emplace_back(in);
            ++mp[in];
        }
        //区间和大于24小时，区间应收缩，左指针向右移
        while (rt - lt + 1 > 86400)
        {
            for (int i = 0; i < lk; ++i)
            {
                if (mp.count(lv[i]))
                {
                    --mp[lv[i]];
                    //如果该国籍人数为0，则从哈希表中移除该国籍
                    if (!mp[lv[i]])
                        mp.erase(lv[i]);
                }
            }
            ++l;
        }
        cout << mp.size() << endl;
        ++r;
    }
    return 0;
}

炫技版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <bits/stdc++.h>
using namespace std;
const int LEN = 3e5 + 10;
//由于国籍最大才为3e5，可以直接用桶数组计数，避免哈希表的开销
int cnt[LEN];
//每次都是移除左指针的船，而船又是按时间升序输入，满足先入先出的规则
//直接用一个队列存放所有船的人即可
queue<int> q;
struct Node
{
    int t_;
    int k_;
} arr[LEN];

#define rt arr[r].t_
#define rk arr[r].k_
#define lt arr[l].t_
#define lk arr[l].k_

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, in, ans = 0, l = 0, r = 0;
    cin >> n;
    while (n--)
    {
        cin >> rt >> rk;
        for (int i = 0; i < rk; ++i)
        {
            cin >> in;
            q.emplace(in);
            if (cnt[in]++ == 0)
                ++ans;
        }
        while (rt - lt + 1 > 86400)
        {
            for (int i = 0; i < lk; ++i)
            {
                int u = q.front();
                q.pop();
                if (cnt[u] && --cnt[u] == 0)
                    --ans;
            }
            ++l;
        }
        cout << ans << endl;
        ++r;
    }
    return 0;
}