【NOIP2016普及组】复赛——海港

题目描述

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

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

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

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

输入格式

第一行输入一个正整数n，表示小K统计了 n艘船的信息。 接下来n行，每行描述一艘船的信息：前两个整数ti和ki分别表示这艘船到达海港的时间和船上的乘客数量，接下来ki个整数x(i,j)表示船上乘客的国家。 保证输入的ti是递增的，单位是秒；表示从小K第一次上班开始计时，这艘船在第 ti 秒到达海港。

输出格式

输出n行，第i行输出一个整数表示第i艘船到达后的统计信息。

数据范围

【输入样例1】

3
1 4 4 1 2 2
2 2 2 3
10 1 3

【输出样例1】

3
4
4

【输入样例2】

4
1 4 1 2 2 3
3 2 2 3
86401 2 3 4
86402 1 5

【输出样例2】

3
3
3
4

分析

看到 每一艘船到达时间为止的24小时(24小时=86400秒）内所有乘船到达的乘客 这句话便可以想到此题会使用栈，而 保证输入的ti是递增的 则能想到将每艘船的乘客依次入栈，不在当前船到达前24小时之内的就把它弹出栈

题目求的是不同的国家的数量，用一个计数器来保存，此外还要用一个数组来存储不同国家的人数，当一个国家人数为0时，则这个国家没人了，计数器减一

AC代码

#include <cstdio>
#include <queue>
using namespace std;

const int MAXN = 1e6;

int t[MAXN], k[MAXN], f[MAXN], m, sum = 0, head = 1;//f为标记数组，记录每个国家的人的出现次数

queue<int> s;//栈用来存储乘客

int main() {
	int n;
	scanf("%d", &n);
	for(int i = 1; i <= n; i ++) {
		scanf("%d %d", &t[i], &k[i]);
		for(int j = 1; j <= k[i]; j ++) {
			scanf("%d", &m);
			if(f[m] == 0) {//如果这个国家的人还没有出现过，则出现了新国家，sum加一
				sum ++;
			}
			f[m] ++;//m国家增加一人
			s.push(m);//将此人入栈
		}
		while(t[head] + 86400 <= t[i]) {//从上一艘船的人数收缩至合适位置，及head号船在i号船的
										//24小时范围之前时，从栈中弹出此船
			for(int j = 1; j <= k[head]; j ++) {//循环弹出乘客
				f[s.front()] --;//当前乘客所在国家人数减一
				if(f[s.front()] == 0) {//如果此国家没人了，则国家数减一
					sum --;
				}
				s.pop();//弹出当前乘客
			}
			head ++;//head往后移一位
		}
		printf("%d\n", sum);//输出sum
	}
	return 0;
}

链接

洛谷P2058