CSP-J-2016-海港

[NOIP2016 普及组] 海港 - 洛谷

---

解题思路：

1.利用结构体数组m设置两个变量，一个记录船只到达的时间arive，一个记录此条船上有多少人much

2.设置一个二维数组member用来存储每条船上的人数的国籍

3.设置一个标记数组统计有多少个不同的国家数量

4.将前3步完成后，便可以将所有信息存储下来，接下来就是开始遍历，题目中，要求求24小时以内的国籍数量，此时第一个问题出现，应该如何确定是24小时内的，可以根据目前的时间，然后往前找找符合要求的，如果此刻的时间-前面的时间是小于86400的，那么再往前找找，直到找到满足条件的时间

5.确定好这个时间，然后从这条船上开始，到目前的船上，将这些船只上的人数进行桶排序，计算数量，输出即可

6.最后将标记数组清零

---

#include
using namespace std;
struct node{
	int arive;//确定船只的时间 
	int much;//确定船只的人数 
}m[1010];
int member[1010][3010];//统计船上人数 
bool flag[1010];//统计国籍 
int main()
{
	int n,num=0,t,k;//num为数组下标 
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>t>>k;//输入时间和人数 
		num++;//存储数组的下标 
		m[num].arive=t;//将时间存入time数组
		m[num].much=k;
		for(int j=1;j<=k;j++)//将国籍输入member数组 
		{
			cin>>member[num][j];
		}
		
		int temp=num;
		while(1)
		{
			temp--;//往前找一找确定24小时内的船只 
			if(temp<=0||m[num].arive-m[temp].arive>=86400)//如果超过了24小时  
			break;//退出循环 
		}
		
		int max=0;//确定国籍的最大值 
		for(int j=temp+1;j<=num;j++)
		{
			for(int h=1;h<=m[j].much;h++)
			{ 
				if(max
				max=member[j][h];
				flag[member[j][h]]++;//桶排序标记 
			}
		}
		
		int sum=0;//统计国籍的数量 
		for(int j=1;j<=max;j++)
		{
			if(flag[j]!=0)//如果这个国籍出现了 
			sum++;//计数器增加 
		}
		cout<
		memset(flag,0,sizeof(flag));//将标记数组清零 
	}
	return 0;
} 

---

优化思路：

1.在模拟思路中，发现二维数组无法放下内存十万和三十万的下标，并且一遍遍的桶排序中，耗费时间过长，那么该如何优化呢？

2.仔细观察，其实每艘船到达的时间和国籍是最重要的，人数是可以忽略的，那么只需要建立两个一维数组将这个人到达的时间和国籍存下来即可，定义时间数组tt，和国籍数组contury，接下来重点是，将这个人的国籍当做flag数组的下标，在输入的时候，统计人数，如果flag[contury[num]]==0，说明还没有这个国籍的人，那么出现的国籍数量ans++，然后flag[contury[num]]++，表示这个国籍出现的人数+1

3.这样，我们就可以把出现的国籍个数和该国籍的人数都存储下来了，接着应该判断是否在24小时之内，因为时间t是升序给出的，那么只要每次输入的时间t和tt[temp]比较就行，如果t-tt[temp]<86400，说明在24小时以内，之前统计的国籍数量就是答案，因为船上的人都是24小时内到达的，直接输出ans即可，否则的话当前tt[temp]的时间是位于24小时之外的，那么对应的这个国籍的人数就要-1，每次减1后判断一下，如果这个国籍的人数为0了，那么说明这个国籍的所有人都在24小时以外，那国籍的数量也要-1，ans--，然后temp++，书签继续向前移动，找不在24小时内的时间

4.temp可以一直增加，因为随着t的输入，越来越大，之前都不在24小时内的船只，那以后也更加不在了，遍历的区间也规定了范围，实现了队列先进先出的操作

---

#include
using namespace std;
int tt[100005];//tt数组用来存储每艘船的时间
int contury[300005];//contury数组存国籍 
int flag[100005];//flag数组表示对应国籍的数量 
int main()
{
	int n,t,k,num=0,ans=0,temp=1;//num表示tt数组的下标 
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>t>>k;//输入每艘船的时间和人数
		for(int j=1;j<=k;j++)
		{
			tt[++num]=t;//每艘船的时间存入tt数组
			cin>>contury[num];//将对应的国籍存入contury数组
			
			if(flag[contury[num]]==0)//如果对应的这个国籍没有人的话
			ans++;//国籍的数量加1
			
			flag[contury[num]]++;//对应这个国籍的人数加1 
		}
		while(1)
		{
			if(t-tt[temp]<86400)//如果当前的时间和起点的时间在24小时内 
			break;//结束循环 
			flag[contury[temp]]--;//对应当前这个国籍的人数减1
			
			if(flag[contury[temp]]==0)//如果当前这个国籍没人的话 
			ans--;//国籍的数量减1 
			
			temp++;//书签移动，换下一个人 
		}
		cout<//输出答案 
	}
	return 0;
}