洛谷 P2058 海港 解题报告

P2058 海港

题目描述

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

小K对这些到达海港的船只非常感兴趣,他按照时间记录下了到达海港的每一艘船只情况;对于第\(i\)艘到达的船,他记录了这艘船到达的时间\(t_i\)(单位:秒),船上的乘客数星\(k_i\),以及每名乘客的国籍\(x(i,1), x(i,2),…,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\)行,每行描述一艘船的信息:前两个整数\(t_i\)和\(k_i\)分别表示这艘船到达海港的时间和船上的乘客数量,接下来\(k_i\)个整数\(x(i,j)\)表示船上乘客的国家。

保证输入的\(t_i\)是递增的,单位是秒;表示从小K第一次上班开始计时,这艘船在第\(t_i\)秒到达海港。

保证\(1<=n<=10^5\),\(\sum {k_i}<=3∗10^5\),\(1<=x(i,j)<=10^5\),\(10^9<=t_{i−1}<=ti<=10^9\)

输出格式:

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


昨天听教练说,普及组的题目不怎么考算法,我的内心陡然一惊,那岂不是怎么暴力怎么来?

事实上并不是那么简单的,不考算法,就十分的考思想了,昨天被2016T4魔法阵吓到了于是打算先写写第三题。

今天读完题目,恩?洛谷高性能?怕不是要卡常?那直接暴力来吧。拿个桶把当前的存起来,把船的信息压进队列,交了以后

洛谷 P2058 海港 解题报告

这个,看来事情并没有这么简单,发现人最多有三十万个,那直接存人和船的时间断点好了。

洛谷 P2058 海港 解题报告

尴尬,,,

加一个上下界优化好了,每次遍历桶的时候只遍历到之前出现过得最大的人。

洛谷 P2058 海港 解题报告

好家伙,不能这样搞。

又想了想,如果更新桶的时候某个种类由0变成了1就把答案加1,反之减1,不就刚好保证了300000*2吗

原来正确复杂度是\(O(\sum k)\),所以有时候想练练思想,不妨多做做没有什么算法的题目。


#include <cstdio>
#include <cstring>
int max(int x,int y){return x>y?x:y;}
const int N=100010;
int ans[N],n,t,k,tour[N*3],time[N][2],l=1,r,p=1,now;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&t,&k);
while(time[l][0]<=t-86400&&l<=r)
{
for(;p<=time[l][1];p++)
{
ans[tour[p]]--;
if(!ans[tour[p]]) now--;
}
l++;
}
for(int j=time[r][1]+1;j<=time[r][1]+k;j++)
{
scanf("%d",tour+j);
ans[tour[j]]++;
if(ans[tour[j]]==1)
now++;
}
time[++r][0]=t;
time[r][1]=time[r-1][1]+k;
printf("%d\n",now);
}
return 0;
}

2018.6.18

上一篇:[leetcode]141. Linked List Cycle判断链表是否有环


下一篇:洛谷 P1979 华容道 解题报告