CF B. Uniqueness

原题链接:Problem - B - Codeforces

题意:长度为n的数组,可以删除一段练习的区间,让留下的数都是各不相同的,问最小的删除区间?

思路:二分+滑动窗口.可以想到因为删除的是连续的区间,那么留下的一定是删除区间的左右区间,因为数据小,所以可以n*n的时间复杂度暴力,不断枚举左区间的右端点,然后枚举右区间的左端点,所有set就可以判断.但是可以发现删除区间的长度具有单调性,删的越长,那么就更容易得到满足题意的数组,所以可以二分一下删除区间的长度,每次二分的长度即为x,那么滑动窗口的大小就是x,滑动窗口之外的数放入map,如果map的大小和滑动窗口之外的位置数相同,那么就是符合题意的数组.

//冷静，冷静，冷静
//调不出来就重构
//#pragma GCC optimize(2)
//#pragma GCC optimize("O3")
#include<bits/stdc++.h>
#define count2(x) __builtin_popcountll(x)
#define is2(x) __builtin_ffsll(x)
#define endl '\n'
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll,ll> pii;
const int N=1e6+10,mod=1000000007;
ll p[N];
ll n;
bool is(ll x)
{queue<ll> op;map<ll,ll> st;for(int i=1;i<=n;i++)st[p[i]]++;for(int i=1;i<=n;i++){op.push(p[i]);st[p[i]]--;if(st[p[i]]==0)st.erase(p[i]);if(op.size()<x)continue;if(op.size()>x){st[op.front()]++;;op.pop();}ll len=n-x;if(len==st.size())return 1;}return 0;
}
void Jiuyuan()
{cin>>n;for(int i=1;i<=n;i++)cin>>p[i];ll l=0,r=n;while(l+1<r){ll mid=l+r>>1;if(is(mid))r=mid;else l=mid;}if(is(l))r=l;cout<<r<<endl;
}
int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);ll T=1;
//	cin>>T;while(T--){Jiuyuan();}return 0;
}