数糖纸(离散化)

链接：https://ac.nowcoder.com/acm/contest/372/D
来源：牛客网

题目描述
可能很多人要吐槽为什么标题不是“救救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张的糖纸，共有三张。
总共有1e9的数据，但是数组却只有1e6的大小，所以就需要离散化了。其实要是用map的话也可以不用离散化，但是这个题用map的话会超时，只能离散化了。离散化之后，设置两个指针。如果当前值没有出现过，就r++，知道当前值之前出现过，然后记录最大值。这样之后，在把这一段的值更新为0。
代码如下：

#include<bits/stdc++.h> #define ll long long using namespace std;const int maxx=1e6+100; int a[maxx],b[maxx]; int vis[maxx]; int n;int main() {while(~scanf("%d",&n)){for(int i=1;i<=n;i++) scanf("%d",&a[i]),b[i]=a[i];sort(b+1,b+1+n);int len=unique(b+1,b+1+n)-b-1;for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+1+len,a[i])-b;//离散化for(int i=0;i<=len;i++) vis[i]=0;int l=1,r=1;int ans=0;while(l<=r&&r<=n){while(!vis[a[r]]&&r<=n) {vis[a[r]]=1;r++;}ans=max(ans,r-l);//找到之前出现的值就更新最大值while(vis[a[r]])//这个循环就是将l指针移动到a[r]第一次出现位置的下一个位置{vis[a[l++]]=0;}}printf("%d\n",ans);} }

努力加油a啊，(^o)/~

创作挑战赛新人创作奖励来咯，坚持创作打卡瓜分现金大奖

总结

以上是生活随笔为你收集整理的数糖纸(离散化)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。