洛谷:P2058
OJ: P4953
Ship
:
ti
和乘客国籍的列表 passengers
。n
。ti
、乘客数量 ki
,以及每位乘客的国籍 xi,j
。left
指针来表示当前窗口的左边界。for
循环遍历当前船的所有乘客,将其国籍加入到 freq
数组中,并根据需要更新 distinct
计数。for
循环移除该船的所有乘客国籍,并相应地更新 freq
和 distinct
。distinct
。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; } |