#10042. 「一本通 2.1 练习 8」收集雪花

news/2025/2/15 6:21:38/

题目描述

不同的雪花往往有不同的形状。在北方的同学想将雪花收集起来,作为礼物送给在南方的同学们。一共有 n 个时刻,给出每个时刻下落雪花的形状,用不同的整数表示不同的形状。在收集的过程中,同学们不希望有重复的雪花。你可以从任意 a 时刻开始,在 b 时刻停止。a 到 b 时刻中间的雪花也都将被收集。他们希望收集的雪花最多。

输入格式

第一行一个正整数 n;

第 2 行 n 个非负整数表示 n 个时刻雪花的形状。

输出格式

最多能收集雪花的数量。

样例

输入

5
1 2 3 2 1

输出

3

数据范围与提示

对于 97 分的数据, 1 ≤ n ≤ 1 0 6 , 0 ≤ x i ≤ 1 0 8 1\le n \le 10^6, 0\le x_i \le 10^8 1n106,0xi108。(为原始数据)

应用户要求,加入 3 分的数据, 1 ≤ n ≤ 1 0 6 , 0 ≤ x i ≤ 1 0 9 1\le n\le 10^6,0\le x_i\le 10^9 1n106,0xi109

又是一个不用哈希表的哈希题

大致思路

根据题意,我们需要找到最长不重复子序列,那么就可以借助强大的STL库中的map了

map<int,int> mapp;
unordered_map<int,int> mapp;

其中map基于红黑树实现,而unordered_map基于哈希实现,unordered_map的效率要快于普通的map,但必须在c++11及以上使用

for(int i=1;i<=n;i++){if(mapp[k[i]]==0){sum++;mapp[k[i]]=1;}

查询当前数有没有出现过,若无,则标记出现过。

else {while(mapp[k[i]]!=0){mapp[k[lcnt]]--;sum--;lcnt++;}mapp[k[i]]++;sum++;}

若当前数出现过,则从前面开始找到第一个重复的,过程内的所有数退回标记,即不选
最后max即可

ans=max(ans,sum);

AC CODE

#include<bits/stdc++.h>
using namespace std;
int ans=0,sum=0,n,lcnt=1,k[10000099];
/*unordered_*/map<int,int>mapp;
int main(){cin>>n;for(int i=1;i<=n;i++){![请添加图片描述](https://img-blog.csdnimg.cn/6fdf7246100748e79d1610bc49436ea0.jpeg)cin>>k[i];}for(int i=1;i<=n;i++){if(mapp[k[i]]==0){sum++;mapp[k[i]]=1;}else {while(mapp[k[i]]!=0){mapp[k[lcnt]]--;sum--;lcnt++;}mapp[k[i]]++;sum++;}ans=max(ans,sum);}cout<<ans;return 0;
}

附封面

请添加图片描述


http://www.ppmy.cn/news/603939.html

相关文章

linux环境下快速配置hadoop集群免密登录

背景 在hadoop的日常使用过程中经常需要登录某些机器&#xff0c;如何更好的免密登录呢&#xff1f;这将为我们节省大量的时间 操作 假设你需要在A机器上免密登录B机器&#xff0c;那么你首先要确定B机器下是有秘钥文件的。如何确定是否有&#xff1f;如果你的根目录下有.ss…

docker安装,以及docker源修改,docker-compose安装一条龙

一、docker 安装 1、使用官方安装脚本自动安装 curl -fsSL https://get.docker.com | bash -s docker --mirror Aliyun查看是否安装成功 docker --version成功&#xff1a; rootVM-12-5-ubuntu:~# docker --version Docker version 20.10.11, build dea9396二、docker 更换…

docker安装Mysql5.7以及远程登陆链接配置

1.安装mysql5.7 docker镜像 docker安装&#xff1a;docker安装一条龙 1、拉取官方mysql5.7镜像 docker pull mysql:5.7rootVM-12-5-ubuntu:/# docker pull mysql:5.7 5.7: Pulling from library/mysql ffbb094f4f9e: Pull complete df186527fc46: Pull complete fa362a6aa7b…

c语言中字符串数组的地址存放以及%s输出单个字符导致程序崩溃的问题

代码 总结下c语言中字符串数组的地址存放问题 #include <iostream> using namespace std; #include<bits/stdc.h>int main() {char *s;printf("s的地址是&#xff1a;%d\n", &s);s "hello";char *p s;printf("s存放的是hello的地…

语音识别过程

语音识别的过程

深度学习模型在图像识别中的应用:CIFAR-10数据集实践与准确率分析

文章目录 前言导入所需的库忽略证书验证下载并加载 CIFAR-10 数据集数据预处理构建深度学习模型编译模型模型训练模型评估进行图片识别测试图片运行效果完整代码完结 前言 深度学习模型在图像识别领域的应用越来越广泛。通过对图像数据进行学习和训练&#xff0c;这些模型可以自…

LeetCode 10. Regular Expression Matching python特性、动态规划、递归

前言 本文主要提供三种不同的解法&#xff0c;分别是利用python的特性、动态规划、递归方法解决这个问题 使用python正则属性 import reclass Solution2:# return a booleandef isMatch(self, s, p):return re.match(^ p $, s) ! None 使用递归方法 class Solution(obje…