海港
剑枫 / 2020-07-12 / 默认分类 / 阅读量 36

海港-队列
Problem:D
Time Limit:2000ms
Memory Limit:65535K
Description
小K是一个海港的海关工作人员,每天都有许多船只到达海港,船上通常有很多来自不同国家的乘客。
小K对这些到达海港的船只非常感兴趣,他按照时间记录下了到达海港的每一艘船只情况;对于第i艘到达的船,
他记录了这艘船到达的时间ti (单位:秒),船上的乘客数k,以及每名乘客的国籍x1,x2,x3,x4等;
小K 统计了这N 艘船的信息,希望你帮助计算出每1艘船到达为止的24小时(86400秒)内到达的船上的乘客来自多少个国家?
Input
第1行为一个n,表示有n条船;
接下来有n行,每行前2个数为t和k,表示这艘船的到达时间和船上的旅客数量!
然后是这k个旅客的国籍(x1 x2 x3 .......都是整数)
Output
输出n行,每行代表这艘船到达为止的24小时(86400秒)内到达的船上的乘客来自多少个国家?
t[i]-t[p]<86400,t[i]表示当前船的时间,t[p]表示之前进海港的船!
1<=n,k<=300000; 1<=ti<=1000000000;
Sample Input
例子输入1:
3
1 4 4 1 2 2
2 2 2 3
10 1 3
例子输入2:
4
1 4 1 2 2 3
3 2 2 3
86401 2 3 4
86402 1 5
Sample Output
例子输出1:
3
4
4
例子输出2:
3
3
3
4
————————————————————————————————————————————————————————————————————————————
本题用队列做就行啦,我们用一个结构体来存储到达船只的时间点和国家数,难点就在此,知道了这个就其他都没有问题了。然后我们用队列进行求解。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
————————————————————————————————————————————————————————————————————————————————————————————————————

include<bits/stdc++.h>

using namespace std;
struct person
{

/* data */
int time;
int country;

}; //存储船只到达的时间和人员所属国家
int ans[1000]; //用桶排序来记录人员所属的国家
int main()
{
int n,t,k,x,l,num=0;//num表示的是在一个时间点所到全部人员所属国家的国家数。
queue<person>vis; //定义队列
cin>>n;
person tmp;
for(int i=1;i<=n;i++)
{

  cin>>t>>k;
  for(int j=1;j<=k;j++)
  {
      cin>>x;
      vis.push({t,x});        //记录所到船只的时间点和人员所属国家
      if(ans[x]==0) {num++;}   //记录前面没有到国家数          ans[x]++;            //将同一个国家的人家加起来
  }
  while(t-vis.front().time>=84600)
  {
      tmp=vis.front();
      vis.pop();
      int x1=tmp.country;
      ans[x1]--;                 //如果超过24小时,则无效,将超过24小时这个时间段以外的人员所属国减去。
      if(ans[x]==0) num--;
  }

cout<<num<<endl;

}

return 0;
}