AcWing467. 海港

news/2024/5/20 9:06:19 标签: 算法, 数据结构, 滑动窗口, c++, 开发语言

 输入样例:

3 
1 4 4 1 2 2 
2 2 2 3 
10 1 3

输出样例:

3
4
4

解析: 

        滑动窗口,用队列维护每个乘客的时间和国籍,当新加入一个时间的乘客时,队头弹出24小时前的所有乘客,并且cnt数组记录当前统计的乘客国籍。

代码:

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m,k,x;
int cnt[N],res;
queue<pair<int,int>>q;
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++){
    	scanf("%d%d",&m,&k);
    	while(q.size()&&q.front().first<=m-86400){	//弹出24小时前的乘客 
    		int x=q.front().second;
			q.pop();
			if(cnt[x]==1) res--;
			cnt[x]--;	
		}
    	for(int j=0;j<k;j++){						//加上当前的乘客 
    		scanf("%d",&x);
    		if(cnt[x]==0) res++;					//统计国籍 
    		cnt[x]++;
    		q.push({m,x});
		}
		cout<<res<<endl;
	}
    return 0; 
} 

http://www.niftyadmin.cn/n/280538.html

相关文章

每日学术速递4.28

CV - 计算机视觉 | ML - 机器学习 | RL - 强化学习 | NLP 自然语言处理 Subjects: cs.CV 1.StepFormer: Self-supervised Step Discovery and Localization in Instructional Videos(CVPR 2023) 标题&#xff1a;StepFormer&#xff1a;教学视频中的自我监督步骤发现和定位…

Windows10本地搭建网站教程 - 内网穿透发布公网访问

文章目录 概述1. 搭建一个静态Web站点2. 本地浏览测试站点是否正常3. 本地站点发布公网可访问3.1 安装cpolar内网穿透3.2 创建隧道映射公网地址3.3 获取公网URL地址 4. 公网远程访问内网web站点5. 配置固定二级子域名5.1 保留二级子域名5.2 配置二级子域名 6. 测试访问二级子域…

JS手写实现Promise.all

Promise.all() 方法接收一个 Promise 对象数组作为参数&#xff0c;返回一个新的 Promise 对象。该 Promise 对象在所有的 Promise 对象都成功时才会成功&#xff0c;其中一个 Promise 对象失败时&#xff0c;则该 Promise 对象立即失败。 本篇博客将手写实现 Promise.all() 方…

Java基础部分面试题(2023最新)

一、Java概述 1. 谈谈你对 Java 平台的理解&#xff1f; ① 平台无关性&#xff08;一次编译到处运行&#xff09; ② GC&#xff08;垃圾自动回收机制&#xff0c;不像C那样需要手动去释放堆内存&#xff09; ③ 语言特性&#xff08;泛型、反射、Lambda 表达式&#xff09; …

【Python基础练习100题--第一篇:文件篇】

前言 这些题都是在B站的练习题&#xff0c;链接在这 对于刚学python的新手来说十分的适合&#xff0c; 可以加强和巩固我们的基础。 嘿嘿 一起噶油吧&#xff01;&#x1f349; &#x1f349;1.对学生成绩排序 # 这里对字典进行排序&#xff0c;同事使用到了sorted函数 # 这…

ros基础笔记

1创建工作空间 catkin_init_workspace 将文件夹初始化成ros文件 编译工作空间catkin_make vi ~/.bashrc 加入环境变量bashrc一下在任何终端都生效 catkin_create_pkg learning_communication通讯机制 std_msgs数据结构 rospy roscpp catkin_create_pkg mbot_description ur…

错题笔记第一篇

目录 1. strlen的用法2. case3. switch4. 二分查找 1. strlen的用法 正确答案 &#xff1a;C strlen计算的是字符串的长度&#xff0c;二字符串是以\0结尾&#xff0c;而咱们并没有存储\0&#xff0c;后序的空间是未知的&#xff0c;strlen找不到\0就会一直找&#xff0c;所以它…

容器镜像的导入导出

容器镜像的导入导出 第1关&#xff1a;导入导出容器 任务描述 ​ 本关任务是学习导入导出容器&#xff0c;要求学习者参照示例完成将busyboxContainer容器的文件系统保存为一个tar包&#xff0c;通过该tar包导入一个busybox:v1.0镜像。 相关知识 将 "容器的文件系统&…