官方题解｜强迫症序列

题目大意

一个序列删除一个最小的区间，使得剩下的数俩俩各不相同。

解题思路

对于前$60\%$的数据，可以直接暴力 $O(n^2)$ 枚举。枚举每次删除的长度 $Len$ 然后剩下的数再扫一边，判断有没有重复就可以获取答案。

$100\%$数据的解法用二分答案的思想，二分答案然后用 $O(n)$ 的时间确定一下答案是否合法就可以。怎么用 $O(n)$ 时间判断呢。注意到，重复的意思就是出现两次以上，那么只有在出现一次和出现二次之间变化的时候才会影响答案的统计。那么统计一下每个数的出现次数，在扫答案的时候维护就可以了。可以用 $unordered\_map$ 或者 离散化处理 1e9 的数据（详细看代码就可以了）

参考代码

(unordered_map)

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5+5;
int a[maxn];
int n;
int cnt;// 记录有几个是重复的 
unordered_map<int,int>mp;
bool check(int len){
	bool flag = false;
	for(int i=1;i<=len;i++){
		mp[a[i]]--;
		if(mp[a[i]]==1)cnt--;
	}
	if(cnt == 0) flag = true;
	for(int i=len+1;i<=n;i++){
		mp[a[i-len]]++;
		if(mp[a[i-len]]==2)cnt++;
		mp[a[i]]--;
		if(mp[a[i]]==1)cnt--;
		if(cnt==0)flag = true;
	}
	for(int i=n-len+1;i<=n;i++){
		mp[a[i]]++;
		if(mp[a[i]]==2)cnt++;
	}
	return flag;
}

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		mp[a[i]]++;
		if(mp[a[i]]==2){
			cnt++; 
		} 
	}
	int ans = 0;
	int l=0,r=n;
	while(l<=r){
		int mid = (l+r)>>1;
		if(check(mid)){
			ans = mid;
			r = mid-1;
		}else{
			l = mid+1;
		}
	}
	printf("%d\n",ans);
	return 0; 
} 

离散化

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5+5;
int a[maxn];
int n;
int cnt;// 记录有几个是重复的 

int pos[maxn];
int b[maxn];
int mp[maxn];

bool check(int len){
	bool flag = false;
	for(int i=1;i<=len;i++){
		mp[pos[i]]--;
		if(mp[pos[i]]==1)cnt--;
	}
	if(cnt == 0) flag = true;
	for(int i=len+1;i<=n;i++){
		mp[pos[i-len]]++;
		if(mp[pos[i-len]]==2)cnt++;
		mp[pos[i]]--;
		if(mp[pos[i]]==1)cnt--;
		if(cnt==0)flag = true;
	}
	for(int i=n-len+1;i<=n;i++){
		mp[pos[i]]++;
		if(mp[pos[i]]==2)cnt++;
	}
	return flag;
}

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		b[i] = a[i];
	}
	sort(b+1,b+1+n);
	int tot = unique(b+1,b+1+n)-b;
	for(int i=1;i<=n;i++){
		pos[i] = lower_bound(b+1,b+1+tot,a[i])-b;
	}
	for(int i=1;i<=n;i++){
		mp[pos[i]]++;
		if(mp[pos[i]]==2){
			cnt++; 
		} 
	}
	int ans = 0;
	int l=0,r=n;
	while(l<=r){
		int mid = (l+r)>>1;
		if(check(mid)){
			ans = mid;
			r = mid-1;
		}else{
			l = mid+1;
		}
	}
	printf("%d\n",ans);
	return 0; 
}