P2058 [NOIP2016 普及组] 海港
坑点:
- 一开始的思路是直接建一个队列,如果队里有这个国家的人那么就不进队,根据时间不断删除队首,查询队列的 size。
很容易看出这个思路不可行。
因为这个时刻队列中有这个国籍的人,下一次就不一定是这一个了 - 那我们记录此时队列中有几个此国籍的人,根据时间删除时就是这个编号-1,如果减成0,size-1。如果队列里一开始没有,就让 size+1。
一定要先减后加!!!降低时间复杂度
代码:
#include<bits/stdc++.h>
using namespace std;
queue<pair<int,int> >qt;//记录people的队列
//pair的first存储这个人进入海港的时间,second存储这个人的国籍
int cnt[5000100];
int sizeq=0;
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
int t,k;
cin>>t>>k;
while(!qt.empty()&&t-qt.front().first>=86400) {
int se=qt.front().second;
cnt[se]--;
if(cnt[se]==0) sizeq--;
qt.pop();
}
for(int j=1;j<=k;j++)
{
int cn;
cin>>cn;
cnt[cn]++;
if(cnt[cn]==1)
sizeq++;
qt.push({t,cn});
}
cout<<sizeq<<endl;
}
return 0;
}
标签:cnt,qt,int,模拟题,队列,注意事项,size,合集,cn
From: https://www.cnblogs.com/lazy-ZJY0307/p/18407373