noip2016普及组--海港
题目:
这道题主要的思路是用一个结构体队列存每个人来的时间和他的国籍,用一个数组存每个国籍的人来的次数,是第一次来总数sum便加一。如果这个队列的第一个人到达的时间超过了一天,就把这个人删除,同时数组[这个人的国籍]减一,当这个国籍的人数为0时,sum减一,每检查一个人就删除一个人,直到队列的首位时间不超过一天,循环结束。
代码如下
#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
struct passengers
{
int pt,px;//存入每个乘客的时间和国籍
};
queue <passengers> ship;//存入每个人的到来时间和国籍
int ans[100005];//存入每个国籍的人数
int main()
{
int n;
cin>>n;
int sum=0;
while(n--)
{ int t,k,x;
scanf("%d%d",&t,&k);//船来的时间和人数
for(int i=0;i<k;i++)
{
scanf("%d",&x);//k个人每个人的国籍
passengers m;
m.pt=t;
m.px=x;
ship.push(m);//把每个人存入队列
ans[x]++;
if(ans[x]==1)//如果是第一次来
sum++;
}
while(1)
{
int a,b;
a=ship.front().pt;//队列第一个人的时间和国籍
b=ship.front().px;
if(t-a<86400)//没超过第一天
break;
ans[b]--;//这个人对应减一
if(ans[b]==0)
sum--;
ship.pop();//删除这个人
}
printf("%d\n",sum);
}
return 0;
}
借鉴于 **** 青天璇