yltx's blog

yltx's blog

Κοιτάζοντας πάνω στον έναστρο ουρανό, κάτω στη γη.

题解 CF1208B 【Uniqueness】

posted on 2019-08-26 22:04:31 | under 题解 |

这个题实际上可以two-pointers或者二分答案

很明显,后者好写一些。

于是我们二分删掉的区间长度,枚举区间开始的端点,再 $O(n)$ 判断。

5min写出了下面的代码:

#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,然而我们数字的个数不多,实际上离散化一下完全可以桶解决。

于是有了离散化的代码:

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