比赛 至少完成十道练习 评测结果 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的。*/