P2058 海港

题目原文及输入/输出格式

题目描述

小K是一个海港的海关工作人员，每天都有许多船只到达海港，船上通常有很多来自不同国家的乘客。

小K对这些到达海港的船只非常感兴趣，他按照时间记录下了到达海港的每一艘船只情况；对于第$i$艘到达的船，他记录了这艘船到达的时间$ti$ (单位：秒)，船上的乘 客数$k_i$，以及每名乘客的国籍 $x{i,1}, x{i,2},…,x{i,k}$。

小K统计了$n$艘船的信息，希望你帮忙计算出以每一艘船到达时间为止的24小时(24小时=86400秒）内所有乘船到达的乘客来自多少个不同的国家。

形式化地讲，你需要计算$n$条信息。对于输出的第$i$条信息，你需要统计满足$ti-86400<t_p<t_i$的船只$p$，在所有的$x{p,j}$中，总共有多少个不同的数。

思路

将所有航班的船只信息（到达时间和人）储存下来，而后对所有船只进行遍历，每次寻找该次遍历下船只到达时间24小时内的其他到达海港的船只，最后清点国籍计算答案。

70分代码

完全按照思路来模拟，用vector存储所有的人，保存在结构体内，最后计算答案。清点国籍的部分用Hash Map。

struct ship{
	int time;
	vector<int> people;
}S[100010]; 

int n;
map<int, int> check;

int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		int t, num;
		cin>>t>>num;
		S[i].time=t;
		for(int j=1;j<=num;j++){
			int temp;
			cin>>temp;
			S[i].people.push_back(temp);
		}
	}
	for(int i=1;i<=n;i++){
		check.clear();
		int ans=0;
		for(int j=i;S[i].time-S[j].time<86400 && j>0;j--){
			for(int k=0;k<S[j].people.size();k++){
				if(check[S[j].people[k]]==0) ans++;
				check[S[j].people[k]]=check[S[j].people[k]]+1;
			}
		}
		cout<<ans<<endl;
	}
    return 0;
}

优化

70分肯定是不满足的，我们还有进行一(亿)点优化。首先有几个问题需要思考：是存船只的数据好还是只存人的数据，然后把船只的到达时间作为人的属性存储好？还有就是是不是每个人的数据都要存下来？第二个问题的答案很明确，显然不是每个人的数据都必须存下来，本题中只需要某次航班24小时内的船只信息，所以人数据的删除和添加是比较多的，所以第一个问题我认为是储存人的数据更好。所以做出以下改动：

1. 取消船只的结构体，进而改成人的数据。
2. 使用队列，每次遍历某个航班时，先搜查队列信息，将24小时之后的信息全部删除，然后再统计本次航班数据。
3. 由2可知，某次航班的答案必定和上一班的答案有关系，因为这一班的答案是通过上一班的答案的删除和新增得来的。

AC代码

结构体person存人的信息，让入队列P中。最后遍历中对之前24小时之外的航班和本次航班的国籍统计还是使用Hash Map。

struct person{
	int time, nation;
	
	person(int t, int n){
		this->time=t;
		this->nation=n;
	}
};

int n, ans;
map<int, int> check;
queue<person> P;

int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		int time, num;
		cin>>time>>num;
		while(!P.empty()){
			person p=P.front();
			if(p.time+86400 <= time){
				check[p.nation]--;
				if(check[p.nation]==0) ans--;
				P.pop();
			}else break;
		}
		
		for(int j=1;j<=num;j++){
			int a;
			cin>>a;
			if(check[a]==0) ans++;
			check[a]++;
			P.push(person(time, a));
		}
		
		cout<<ans<<endl;
	}
    
    return 0;
}