洛谷P2058 [NOIP2016 普及组] 海港（c嘎嘎）

题目链接：

难度：普及

样例分析：

解题思路：用队列记录输入的时间和国家，然后与队头的时间进行比较大于等于86400，那么这次就不是同一天，这个人所在国家数减一，如果这个人走后这个国家的人减为0，那么之前记录的ans就要减1 ，并且与下一个人比较，直至差值<86400

下面奉上代码：

#include<bits/stdc++.h>  // 万能头文件
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;     
int n;//n艘船 
int t,k;//时间和乘客数量 
int nation[N];//用来记录国籍个数 
int ans;//用来记录答案 

struct node{
	int c,t;
}; //用结构体来记录国家和时间 

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    
    cin >> n;//输入n组数据 
    
    queue<node>q;//用队列来存结构体 
    node h;
    
    while(n--)
    {
        cin >> t >> k;//读入每组船到达的时间和乘客数量 
        while(!q.empty())//队列非空就执行 
        {
       	    h = q.front();//取出队头因为输入时间递增保证取出的时间也是递增的 
       	   if(h.t + 86400 <=t)//不是同一天的船就要对队列和答案更新 
       	   {
       	   	    nation[h.c]--;//这个国籍的人数人数减一 
       	   	    if(nation[h.c] == 0) ans --;
       	   	    q.pop();//不是同一天的人移除队列 
       	   	    continue;//因为是单调递增，所以后面可能还有同一天的,继续去找 
		   }
		   break;//如果现在这个在24小时内，后面的肯定也符合条件，直接退出
    	}
		   for(int i=1; i<=k; i++)  //查完前面后，我们就对这只本身的船进行统计
		   {
		   	    int x;
		   	    cin >> x;//输入国籍 
		   	    h.c = x,h.t = t;//存入结构体 
		   	    q.push(h);//存入队列 
		   	    nation[x] ++;//把这个国籍的人加1（桶排序） 
		   	    if(nation[x] == 1) ans ++;//第一次出现这个国籍更新答案 
	      } 
	    	
	   cout<<ans<<'\n';  	
	}

    return 0;  
}