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;
}