P2058题解

思路

以下记

sum_i

为在一天内国籍

i

有抵达的人数，

num

为一天内抵达的人的国籍数。

每一艘船上的每一个人到达时，若当前到达的是国籍

x

的乘客，且

sum_x = 0

，那么就将

sum_x+1

，且

num+1

，接着，让这个人的国籍以及到达时间入队，并把队尾指针

+1

。

然后，把在一天之前到达的人弹出队列。如果当前的人国籍为

y

且在一天之前到达（即当前时间减去到达时间大于等于

86400

），那么

sum_y-1

。如果此时

sum_y=0

，那么

num-1

。然后队头

+1

再处理下一个人。

solution

CPP

#include<bits/stdc++.h>
#define ll long long
const int N = 5e5+5;
using namespace std;
ll n,t,k,x,l,r;
ll a[N],f[N],tme[N];
ll num;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>t>>k;
		while(k--){
			tme[++r]=t;
			cin>>a[r];
			if(!f[a[r]])num++;
			f[a[r]]++;
		}
		while(t-tme[l]>=86400){
			if(!--f[a[l++]])num--;
		}
		cout<<num<<"\n";
	}
	return 0;
}

文章操作

思路

solution

相关推荐

评论

P2058题解