首页 > 代码库 > UVa11572 Unique Snowflakes (滑动窗口)

UVa11572 Unique Snowflakes (滑动窗口)

链接:http://vjudge.net/problem/UVA-11572

 

分析:维护一个set即可。

 1 #include <cstdio> 2 #include <algorithm> 3 #include <set> 4 using namespace std; 5  6 const int maxn = 1000000 + 5; 7  8 int n, a[maxn]; 9 10 int main() {11     int T;12     scanf("%d", &T);13     while (T--) {14       scanf("%d", &n);15       for (int i = 0; i < n; i++) scanf("%d", &a[i]);16       set<int> s;17       int L = 0, R = 0, ans = 0;18       while (R < n) {19         while (R < n && !s.count(a[R])) s.insert(a[R++]);20         ans = max(ans, R - L);21         s.erase(a[L++]);22       }23       printf("%d\n", ans);24     }25     return 0;26 }

 

UVa11572 Unique Snowflakes (滑动窗口)