285484026

【UVA 11572】 唯一的雪花 滑动窗口
昨天学弟和我说了一下滑动窗口,今天就看了一下,然后发现似乎是挺简单的。输入一个长度为n(n<=1e6)的序列...
扫描右侧二维码阅读全文
01
2018/10

【UVA 11572】 唯一的雪花 滑动窗口

昨天学弟和我说了一下滑动窗口,今天就看了一下,然后发现似乎是挺简单的。

输入一个长度为n(n<=1e6)的序列A,找到一个尽量长的连续子序列AL~AR,使得该序列中没有相同元素。输出最大长度。

题解:
恩,大致思路就是维护两个指针表示这个序列的左端点和右端点,然后如果最右边的右边那一个在这个数列没有出现过就将右端点向右移动,如果出现了重复的就将左端点向右移动并且每次统计答案。

但是怎么统计这个元素在序列中出现过没呢?就用set统计就好了。
代码:

#include <iostream>
#include <cstdio>
#include <set>

using namespace std;

int N,a[10000000],L = 1,R = 1,ans;

set<int>s;

int main()
{
    scanf("%d",&N);
    
    for(int i = 1;i <= N;i++)
        scanf("%d",&a[i]);
    
    while(R < N)
    {
        while(R < N && !s.count(a[R])) s.insert(a[R++]);
        ans = max(ans,R - L);
        s.erase(a[L++]);
    } 
    printf("%d",ans);
    return 0;
}
Last modification:October 1st, 2018 at 08:13 am
If you think my article is useful to you, please feel free to appreciate

Leave a Comment