Uva 11572 唯一的雪花

题目链接：https://uva.onlinejudge.org/external/115/11572.pdf

题意：找到一个尽量长的连续子序列 A_l~ A_R ，使得该序列没有相同的元素。

分析：枚举超时，怎么优化呢？当我不停的将右端点右移，当我移不动的时候，说明之前的 l ~ r 里面有一个和 r++的元素相同。

但是，不代表 l ~ r 就没有用了，他本身还是有作用的，只要将 l 右移即可。这样，单看这里，时间复杂度为O(n) ，

然后就是查看 r++ 的元素是否和前面的相同，用 set 集合，时间复杂度是 O(log n) ;

 #include <bits/stdc++.h>

 using namespace std;

 const int maxn =  + ;

 int a[maxn];

 int main()

 {

     int t;

     cin>>t;

     while(t--) {

         int n;

         cin>>n;

         for(int i=;i<n;i++)

             cin>>a[i];

         set<int> s;

         int L = ;

         int R = ;

         int ans = ;

         while(R<n) {

             while(R<n&&!s.count(a[R])) s.insert(a[R++]);

             ans = max(ans,R-L);

             s.erase(a[L++]);

         }

         cout<<ans<<endl;

     }

     return ;

 }

巴特西

Uva 11572 唯一的雪花

最新文章

热门文章