题目描述
不同的雪花往往有不同的形状。在北方的同学想将雪花收集起来,作为礼物送给在南方的同学们。一共有n个时刻,给出每个时刻下落雪花的形状,用不同的整数表示不同的形状。在收集的过程中,同学们不希望有重复的雪花。你可以从任意 a时刻开始,在 b时刻停止。a到 b时刻中间的雪花也都将被收集。他们希望收集的雪花最多。
输入格式
第一行一个正整数 ;
第 2行n个非负整数表示n个时刻雪花的形状。
输出格式
最多能收集雪花的数量。
样例
输入样例
5
1 2 3 2 1
输出样例
3
#include<bits/stdc++.h>
using namespace std;
int a[1000005];
map<int,int>m;
int main(){
int n;
int j=1,ans=0;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
if(m.find(a[i])!=m.end()){ //如果当前这个数曾经出现过;
while(a[j]!=a[i]) //a[j]枚举第一个出现的与a[i]相同的数;
m.erase(m.find(a[j++])); /*把a[j]以前的数全部删掉,包括a[j],
因为以前的最大值已经放进ans里面了,不需要使用,只需要统计a[j+1]到a[i]的情况就好了*/
j++; //a[j]也不需要了;
}
else m[a[i]]=1; //否则直接打标记即可
ans=max(ans,i-j+1);
}
printf("%d",ans);
return 0;
}
收集雪花(map)的更多相关文章
-
「LOJ#10042」「一本通 2.1 练习 8」收集雪花 (map
题目描述 不同的雪花往往有不同的形状.在北方的同学想将雪花收集起来,作为礼物送给在南方的同学们.一共有 n 个时刻,给出每个时刻下落雪花的形状,用不同的整数表示不同的形状.在收集的过程中,同学们不希望 ...
-
#10042. 「一本通 2.1 练习 8」收集雪花 || 离散化 || 双指针法 || C++ || LOJ
题目:#10042. 「一本通 2.1 练习 8」收集雪花 看到网上没有这道题的题解,所以写一下. 要标记数字是否存在,看到x<=1e9,所以考虑用离散化,然后开一个last数组,last[i] ...
-
【hash表】收集雪花
[哈希和哈希表]收集雪花 题目描述 不同的雪花往往有不同的形状.在北方的同学想将雪花收集起来,作为礼物送给在南方的同学们.一共有n个时刻,给出每个时刻下落雪花的形状,用不同的整数表示不同的形状.在收集 ...
-
LOJ10042 收集雪花
题意 不同的雪花往往有不同的形状.在北方的同学想将雪花收集起来,作为礼物送给在南方的同学们.一共有 n 个时刻,给出每个时刻下落雪花的形状,用不同的整数表示不同的形状.在收集的过程中,同学们不希望有重 ...
-
[LOJ#10042] 收集雪花
题目链接: 点我 题目分析: 双指针扫描可以保证在\(O(n)\)的时间复杂度内处理这道题.另外,虽然这个题标签是\(hash\),但是字符串\(hash\)是可以卡掉的,所以建议直接离散化. 维护两 ...
-
Map接口,Map.Entry,hashMap类,TreeMap类,WeakHashMap。
Collection接口之前接触过,每次保存的对象是一个对象,但是在map中保存的是一对对象,是以key->value形式保存的. 定义: public interface Map<K,V ...
-
使用java8的lambda将list转为map(转)
常用方式 代码如下: public Map<Long, String> getIdNameMap(List<Account> accounts) { return accoun ...
-
java类集: collection, list , set, map
都在java.util包里.容器:装各种对象. Collections类 : 集合工具类, 提供了一些静态方法, 方法里的参数是List等. Colection接口,子接口主要有: Set: 内容 ...
-
java8中用流收集数据
用流收集数据 汇总 long howManyDishes = menu.stream().collect(Collectors.counting()); int totalCalories = men ...
随机推荐
-
itoa函数的递归实现(二级指针实现)
问题提出 <C Programming Language>书中在递归这一节预留了两个使用递归实现的函数,其中itoa函数是用来将一个整数转换为一个字符串.书中已有使用循环实现的版本,但是直 ...
-
7-ajax的同步和异步?
同步和异步统一根据send()执行的位置来实现分割逻辑同步:1.send()后统一不会被执行,直到http事务完成之后才会之后后续逻辑.2.堵塞send()方法的逻辑.异步:1.send()后面照样执 ...
-
第一百二十七节,JavaScript,JSON数据类型转换,数据转换成字符串,字符串转换成数据
第一百二十七节,JavaScript,JSON数据类型转换,数据转换成字符串,字符串转换成数据 学习要点: 1.JSON语法 2.解析和序列化 前两章我们探讨了XML的结构化数据,但开发人员还是觉得这 ...
-
大数据平台Hive数据迁移至阿里云ODPS平台流程与问题记录
一.背景介绍 最近几天,接到公司的一个将当前大数据平台数据全部迁移到阿里云ODPS平台上的任务.而申请的这个ODPS平台是属于政务内网的,因考虑到安全问题当前的大数据平台与阿里云ODPS的网络是不通的 ...
-
②泡茶看<;数据结构>;,喜欢看源码-栈ADT
前言 听着天籁,我是个音乐迷.时间充实着,会过得很快.我马上也可以到傍晚的时候去乐室吹我心爱的萨克斯. 嘟嘟嘟... 我会吹一首简单的歌咯,哈哈我想到了一个神奇的比喻,待会说. 栈ADT模型(又称LI ...
-
从Java的角度简单修复Cookie越权漏洞
技术实在是有限,讲解cookie越权的时候可能有点简单和粗糙.这里就简单记录学习下. 首先自己写一段存在漏洞的代码code: sendCookie.java package cookie; impor ...
-
pytest 6 生成html报告
前言:pytest-HTML是一个插件,pytest用于生成测试结果的HTML报告.兼容Python 2.7,3.6 1.github上源码地址[https://github.com/pytest-d ...
-
hdu 2476";String painter";(区间DP)
传送门 https://www.cnblogs.com/violet-acmer/p/9852294.html 题意: 给定字符串A,B,每次操作可以将字符串A中区间[ i , j ]的字符变为ch, ...
-
SQLServer2005中的CTE递归查询得到一棵树
最近研究了一下CTE递归查询,感觉这个CTE递归查询蛮好用的,在网上找到了一个比较好的例子,测试例子如下 use City; go create table Tree ( ID ,) primary ...
-
linux终端无打印信息的实现
linux启动时会又大量信息打印,若要使启动信息不打印,需修改内核中两处: 1. 内核配置项. CONFIG_SERIAL_ATMEL_CONSOLE=y //去掉终端配置选项.2. 内核解压缩 ...