首页 > 代码库 > 【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】海港
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。