本文共 1219 字,大约阅读时间需要 4 分钟。
链接: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#define ll long longusing 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)/~
转载地址:http://futvi.baihongyu.com/