做推广要知道的网站,深圳微商城网站制作费用,中机建设一公司网站,前端后端P2058 海港 题解 这道题就是给出你n艘船#xff0c;让你看看以当前船停靠时间为截止时间#xff0c;24h以内乘客来自多少不同的国家 一开始会想到来一艘船就记录下本船的到达时间#xff0c;到达人数#xff0c;以及乘客的国籍 但是你会发现这很占空间 而且船只进来的顺序都…P2058 海港 题解 这道题就是给出你n艘船让你看看以当前船停靠时间为截止时间24h以内乘客来自多少不同的国家 一开始会想到来一艘船就记录下本船的到达时间到达人数以及乘客的国籍 但是你会发现这很占空间 而且船只进来的顺序都是递增的也就是一旦当前船只不需要某个24h以外的船只那么这个24h以外的船只就没用了所以根本没有必要记录这么多 于是乎我们想到了队列 队列存放每个乘客的信息到达时间t国籍g 我们再开一个natin数组记录每个国家有多少个乘客 对于新进入的船只如果乘客队列里非空那我们就从头看一看不断枚举队首 1如果当前乘客已经超时了就说明他已经没有利用价值了natin[now.g]--并且把他出队如果natin[now.g]减少到0也就是说明24h内已经没有这个国家的人了ans就要-- 2如果当前乘客没有超时那么他后边的乘客也一定不会超时跳出队列 当然新进的船只里面也有一堆新乘客对吧 我们把这些新乘客也入队记录他们的国籍如果一旦一个国籍的人数由0-1那么就说明来了一个新国籍的人ans要 代码 #includebits/stdc.husing namespace std;int n,ti,ki,x;
int ans;
int natin[300010];
struct node
{int t;int g;
};
queuenodeboat;int main()
{scanf(%d,n);for(int i1;in;i){scanf(%d%d,ti,ki);while(!boat.empty()){node nowboat.front();if(now.tti-86400){natin[now.g ]--;if(natin[now.g ]0) ans--;boat.pop();continue; //一旦这个乘客超时那么他后边的乘客也有可能超时continue就忽略了跳出队列的break }break; //一旦这个乘客不超时那么就不会执行if语句直接跳出 }for(int j1;jki ;j){scanf(%d,x);node now;now.t ti;now.g x;boat.push(now);natin[x];if(natin[x]1) ans;}printf(%d\n,ans);}return 0;
} 转载于:https://www.cnblogs.com/xiaoyezi-wink/p/11095210.html
