cf1208B B. Uniqueness（1500）
该题要逆向思维， 不看删除的， 要看保留的。
讲解
#include<bits/stdc++.h>using namespace std;const int maxn = 2e3+50;const int inf = 0x3f3f3f3f;int a[maxn];map<int, int>p;set<int>book2;int main(){ios_base::sync_with_stdio(false);int n;cin>>n;for(int i = 1;i <= n;i++){cin>>a[i];}int ans = inf;// 初始化答案int l = 1;p.clear();book2.clear();ans = 333333;while(l <= n){if(p[a[l]]){break;}else p[a[l]] = l;l++;}l--;//左面保留部分的上限ans = n-l;int r = n;while(r >= 1){if(book2.count(a[r]))// 如果该数在右半边出现过，且肯定没在左半边出现过{ans = min(ans, r-l);//取小 结束break;}else book2.insert(a[r]);// 否则标记一下该数if(p[a[r]] && l >= p[a[r]])// 如果左右出现重复的， 去掉左面的{ans = min(ans, r-l);l = p[a[r]] -1;}r--;}cout<<ans;return 0;}
不念不忘少年蓝@
迈不过友情╰
「爱情、让人受尽委屈。」
系统管理员
傷城~
还没有评论，来说两句吧...