当前位置： 移动技术网 > IT编程>开发语言>C/C++ > 唯一的雪花（Unique snowflakes,UVa 11572）滑动窗口+set

唯一的雪花（Unique snowflakes,UVa 11572）滑动窗口+set

2018年04月09日  | 移动技术网IT编程  | 我要评论

雄霸蛮荒笔趣阁,板栗价格,魏千翔娄艺潇结婚照

输入一个长度为n（n<=10^6）的序列A，找到一个尽量长的连续子序列AL~AR，使得该序列中没有相同的元素。

分析：假设序列元素从0开始编号，所求连续子序列的左端点为L，右端点为R。首先考虑起点L=0的情况。可以从R=0开始不断增加R,相当于把所求序列的右端点往右延伸。当无法延伸（即A[R+1]在子序列A[L~R]中出现过）时，只需增大L，并且继续延伸R。既然当前的A[L~R]是可行解，L增大之后必然还是可行解，所以不必减少R，继续增大即可。

最后考虑“判断是否可以延伸”这个部分。比较容易想到的方法是用一个个STL的set，保存A[L~R]中元素的集合，当R增大时判断A[R+1]是否在set中出现，而R加1时把A[R+1]插入到set中，L+1时把A[L]从set中山粗。因为set的插入删除和查找都是O(logn)的，所以这个算法的时间复杂度为O(nlogn)。代码如下：

#include
#include
using namespace std;

const int maxn = 1000000 + 5;
int A[maxn];

int main(){
    int T,n;
    cin>>T;
    while(T--){
        cin>>n;
        for(int i = 0; i < n; i++){cin>>A[i];       }

        set s;
        int L = 0, R = 0,ans = 0;
        while(R < n){
            while(R

您可能感兴趣的文章:

如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网