设为首页 加入收藏

TOP

唯一的雪花(Unique snowflakes,UVa 11572)滑动窗口+set
2018-03-22 08:49:23 】 浏览:224
Tags:唯一 雪花 Unique snowflakes UVa 11572 滑动 窗口 set

输入一个长度为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
     
       
     
    
   
  
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇使用javah 找不到类文件的解决方法 下一篇QML与C++数据绑定教程

最新文章

热门文章

Hot 文章

Python

C 语言

C++基础

大数据基础

linux编程基础

C/C++面试题目