题解 CF1208B 【Uniqueness】
引领天下
2019-08-26 22:04:31
这个题实际上可以two-pointers或者二分答案
很明显，后者好写一些。
于是我们二分删掉的区间长度，枚举区间开始的端点，再$O(n)$判断。
5min写出了下面的代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,a[2005],l,r,mid,ans=1<<30;
map<int,bool> mp;
bool flag;
inline bool check(int d){
for (int i=1;i<=n;i++){
flag=1;
mp.clear();
for (int j=1;j<i;j++)if(mp[a[j]])flag=0;
else mp[a[j]]=1;
for (int j=i+d;j<=n;j++)if(mp[a[j]])flag=0;
else mp[a[j]]=1;
if(flag)return true;
}
return false;
}
int main(){
scanf("%d",&n);
for (int i=1;i<=n;i++)scanf("%d",&a[i]);r=n-1;
while(l<=r){
mid=(l+r)>>1;
if(check(mid))ans=min(ans,mid),r=mid-1;
else l=mid+1;
}
printf("%d\n",ans);
}
```
我使用了map判重，然后输入输出也没有注意，所以#10T了。
那么怎么优化呢？
我们发现效率瓶颈是map，然而我们数字的个数不多，实际上离散化一下完全可以桶解决。
于是有了离散化的代码：
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N =2005;
int n,a[N],sum[N][N],tot,l,r,mid;
struct Node{
int id,val;
inline bool operator < (const Node&p)const{return val<p.val;}
}num[N];
bool flag;
inline bool check(int d){
for (int l=1;l+d-1<=n;l++){
flag=1;
int r=l+d-1;
for(int j=1;j<=n&&flag;j++)if(sum[n][j]-sum[r][j]+sum[l-1][j]>1)flag=0;//利用前缀和优化判断
if(flag)return true;
}
return false;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++)cin>>num[i].val,num[i].id=i;
sort(num+1,num+1+n);//离散化
num[0].val=-1;
for(int i=1;i<=n;i++)if(num[i].val!=num[i-1].val)a[num[i].id]=++tot;
else a[num[i].id]=tot;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++)sum[i][j]=sum[i-1][j];
sum[i][a[i]]++;
}
r=n;
while(l<=r){
mid=(l+r)>>1;
if(check(mid))r=mid-1;
else l=mid+1;//二分
}
cout<<l<<endl;
return 0;
}
```