比赛 |
至少完成十道练习 |
评测结果 |
AAAAAAAAAAAAAAAAAAAA |
题目名称 |
海港 |
最终得分 |
100 |
用户昵称 |
Emine |
运行时间 |
0.385 s |
代码语言 |
C++ |
内存使用 |
3.75 MiB |
提交时间 |
2017-05-23 18:32:13 |
显示代码纯文本
#include<queue>
#include<string>
#include<cstring>
#include<iostream>
#include<cstdio>
using namespace std;
struct Epic
{
int Time,People;
}nowone,oldone;
queue <Epic> q;
int n,m,form[123456],t,sum,a,b,hit;
int main()
{
freopen("port.in","r",stdin);
freopen("port.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d %d",&a,&b);
nowone.Time=a;//存储当前的时间
for(int j=1;j<=b;j++)
{
scanf("%d",&nowone.People);
q.push(nowone);//把船上的人push进队列
if(!form[nowone.People]) sum++;//看这是不是一个新的国籍
form[nowone.People]++;//这个国籍的人数+1
}
while(1)
{
oldone=q.front();//取当前队列里第一个人的时间
if(nowone.Time-86400>=oldone.Time) //如果这个人在一天以前到来
{
form[oldone.People]--; //就把这个人赶走
if(!form[oldone.People]) sum--;//他的国籍的人数-1
q.pop(); //赶走
}
else break;
}
printf("%d\n",sum);
}
return 0;
}
/*我一开始想的是直接模拟,然而――100%的数据告诉你:你想模拟?超时还是超限,选一个吧!
看来直接模拟是不行的,让我们再仔细看一下题目。
为什么题目给出了∑k?而不是k?(k为每艘船的乘客数)
那么我们是不是可以只存“人”呢?
那么,我们就可以考虑一下队列:
第一,不用考虑上限人数。
第二,快。
第三,我们只需把每人的国籍和时间push进队列,再存储每个国籍出现的次数即可。
当输入一个新的日期时,把一天以前的人pop走,再统计不同的国籍出现的次数,即可。
我们可以把这个港口理解为一个旅馆,每个人只准住86400秒,时间到了就把他赶走,如果这样子理解,
让就好多了。
我选择用队列,只要判断一下加进来的时间有没有和队首的时间相差86400s,如果超过了,
就把之前的那艘船上的人的国家--,在pop掉就行了。但是这一有一个问题:
队列中是存人还是存船呢?当然是存人,不然还要给每艘船一个数组来存人的国家,会TLE的。*/