首页 > 代码库 > 【NOIP2016PJ】【Luogu2058】海港

【NOIP2016PJ】【Luogu2058】海港

点此进入原题

算法:模拟、队列

序:这题本SB在考场上当然只能拿最SB的70分QAQ

题解

本题就是一个队列模拟题

将每艘船编号入队。如果当前的船比队列里存在的船要早24小时,则不断出队并减去相应国籍,剩下的和直接模拟也没什么区别了

(代码用STL的queue写的,方便理解)

代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int N=100005;
vector<int> c[N];
queue<int> q;
int t[N];
int main()
{
    int n,ans=0;
    scanf("%d",&n);
    for(int i=1,k;i<=n;i++)
    {
        scanf("%d%d",&t[i],&k);
        for(;!q.empty()&&t[i]-86400>=t[q.front()];q.pop()) //执行出队操作
            for(int j=0;j<c[q.front()].size();j++) //减去国籍
            {
                num[c[q.front()][j]]--;
                if(!num[c[q.front()][j]]) ans--; //如果该国籍不再存在,ans-1
            }
        q.push(i);
        for(int j=1,x;j<=k;j++)
        {
            scanf("%d",&x);
            c[i].push_back(x);
            if(!num[x]) ans++; //如果国籍第一次出现,ans+1
        }
        printf("%d\n",ans);
    }
}

 

【NOIP2016PJ】【Luogu2058】海港