这个题复制过来真的有点恶心,懒得手打,以后再搬题面吧。
今天我双更了,AC这个题我就完成某谷春令营第一课的作业了(假的)
这个题是个双指针。非常友善。一直往里读入就可以了,遇见不是一条船的乘客输出这一条船前86400秒有多少不同国籍的人,然后从末尾查看,时间差大于等于86400的人清除,切记以上两步不要搞混。这个方法每个乘客只会入队出队一次,乘客最多只有300000人。是完全可行的。
接下来就是人见人爱的代码了:
#include<iostream> #include<cstdio> #include<algorithm> #include<queue> #include<cmath> #include<cstring> using namespace std; long long bj[100005],n,k,t,w,e,zs,s,shu,zshu; struct hehe { long long gj,sj;//gj是国籍,sj是到来的时间 }ck[300005]; int main() { cin>>n; for(int i=0;i<n;i++) { cin>>s; cin>>k; for(int j=0;j<k;j++) { cin>>e; zs++;//第zs个乘客 ck[zs].gj=e;//国籍 ck[zs].sj=s;//到达时间 } } t=1;//头指针 w=1;//尾指针 while(t<=zs)//所有乘客都算过一遍后结束 { if(ck[t].sj!=ck[t-1].sj&&t!=1)//出现了不同船的乘客,说明上一条船前86400秒乘客全部计算过了,现在是在上艘船到达时间之后。 { cout<<shu<<endl;//一定要先输出,不然万一减掉不该减的乘客就会WA掉。 while(ck[t].sj-ck[w].sj>=86400)//是>=不是> { bj[ck[w].gj]--; if(bj[ck[w].gj]==0)//如果这个国籍的乘客已经没有了,这艘船前86400秒的总数--。 { shu--; } w++; } } if(bj[ck[t].gj]==0)//来了新乘客。 { shu++; } bj[ck[t].gj]++;//这个乘客国籍的人数+1; t++;//查看下一个。 } cout<<shu<<endl;//最后一艘船的国籍数。 return 0; }
之前这个题我还直接放弃过呢。现在看看也不难。