NC20863. 数糖纸
描述
可能很多人要吐槽为什么标题不是“救救blabla”了。
怪人PM6喜欢数糖纸，不同的糖纸有不同的颜色，一共有 N 张糖纸，第 i 张糖纸颜色为 Ci ，它们的位置都是固定的。PM6喜欢五彩缤纷的糖纸，所以他不希望有重复的颜色。他有一次机会，可以收集任意一段连续区间内的糖纸。求出PM6最多能收集多少张糖纸。
输入描述
第一行一个正整数 N ，表示共有 N 张糖纸。
第二行共有 N 个正整数，第 i 个正整数表示第 i 张糖纸的颜色 Ci
对于20%的数据：1<=N<=100
对于40%的数据：1<=N<=1000
对于100%的数据：1<=N<=1e6，0<=Ci<=1e9
输出描述
一个整数表示PM6最多能收集多少张糖纸。
示例1
输入:
5 1 2 2 3 4
输出:
3
说明:
PM6可以收集第3到第5张的糖纸，共有三张。pypy3(pypy3.6.1) 解法, 执行用时: 1157ms, 内存消耗: 123900K, 提交时间: 2019-12-26 11:21:28
n = int(input())
candys = [i for i in map(int, input().split(' '))]
res = 1
dic = {}
b = 0
for i, v in enumerate(candys):
if v in dic and dic[v] >= b:
b = dic[v] + 1
dic[v] = i
res = max(res, i - b + 1)
print(res)
C++11(clang++ 3.9) 解法, 执行用时: 359ms, 内存消耗: 13920K, 提交时间: 2020-04-02 15:51:38
#include<iostream>
using namespace std;int a[1000003],n,i,j,ans,f[1000000003];int main(){cin>>n;while(j<n){cin>>a[j];while(f[a[j]])f[a[i++]]=0;f[a[j++]]=1;if(ans<j-i) ans=j-i;}cout<<ans;}
Python3 解法, 执行用时: 1340ms, 内存消耗: 110996K, 提交时间: 2022-03-12 23:39:35
m=int(input())
t=dict()
d=0
res=1
s=list(map(int,input().split()))
for i,v in enumerate(s):
if v in t and t[v]>=d:
d=t[v]+1
t[v]=i
res=max(res,i-d+1)
print(res)