复赛三：海港(port)

洛谷：P2058
OJ: P4953

代码详解

  1. 结构体 Ship：
    • 用于存储每艘船的到达时间 ti 和乘客国籍的列表 passengers。
  2. 输入读取：
    • 首先读取船只的数量 n。
    • 对于每艘船，读取其到达时间 ti、乘客数量 ki，以及每位乘客的国籍 xi,j。
  3. 滑动窗口处理：
    • 使用 left 指针来表示当前窗口的左边界。
    • 对于每艘船：
      • 使用传统的 for 循环遍历当前船的所有乘客，将其国籍加入到 freq 数组中，并根据需要更新 distinct 计数。
      • 检查窗口内最早的船是否超过24小时（86400秒）。如果是，则使用传统的 for 循环移除该船的所有乘客国籍，并相应地更新 freq 和 distinct。
      • 输出当前窗口内的不同国籍数量 distinct。
  4. 优化：
    • 使用 ios::sync_with_stdio(false) 和 cin.tie(NULL) 来加速输入输出操作，以应对较大的输入数据量。

代码实现

 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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
/**************************************************************** 
 * Description: 2016年普及组第三题   海港 
 * Author: Alex Li
 * Date: 2024-10-02 17:28:42
 * LastEditTime: 2024-10-02 17:37:34
****************************************************************/
#include <bits/stdc++.h>
using namespace std;

// 定义船只结构体
struct Ship {
    long long ti;           // 到达时间
    vector<int> passengers; // 乘客国籍
};

int main(){
    freopen("port.in","r",stdin);
    freopen("port.out","w",stdout);
    
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    vector<Ship> ships(n);

    // 读取所有船只的信息
    for(int i = 0; i < n; ++i){
        cin >> ships[i].ti;
        int ki;
        cin >> ki;
        ships[i].passengers.resize(ki);
        for(int j = 0; j < ki; ++j){
            cin >> ships[i].passengers[j];
        }
    }

    // 初始化频率数组和其他变量
    // 假设国籍编号从1到100000
    // 根据题目保证1≤xi,j≤10^5
    // 如果国籍编号可能更大，考虑使用更大的数组或其他数据结构
    vector<int> freq(100001, 0); 
    int distinct = 0;
    int left = 0; // 滑动窗口的左指针

    // 逐一处理每艘船
    for(int i = 0; i < n; ++i){
        // 添加当前船的乘客国籍
        for(int j = 0; j < ships[i].passengers.size(); ++j){
            int x = ships[i].passengers[j];
            if(freq[x] == 0){
                distinct += 1;
            }
            freq[x] += 1;
        }

        // 移动左指针，排除不在24小时窗口内的船只
        while(left <= i && ships[left].ti <= ships[i].ti - 86400){
            // 移除船只left的乘客国籍
            for(int j = 0; j < ships[left].passengers.size(); ++j){
                int x = ships[left].passengers[j];
                freq[x] -= 1;
                if(freq[x] == 0){
                    distinct -=1;
                }
            }
            left +=1;
        }

        // 输出当前的不同国籍数量
        cout << distinct << "\n";
    }

    return 0;
}
Previous Topic
Back to Lesson
Next Topic