B. Uniqueness

B. Uniqueness

给定一个序列,要求删除一段连续子段,满足删掉子段后每个元素唯一

求最小子段长度

枚举起点,二分子段长度

记得先sort 再unique

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define si signed
#define endl '
'
#define sc(x) scanf("%I64d",&x);
#define read(A) for(int i=1;i<=n;i++)scanf("%I64d",&A[i]);
#define P pair<int,int>
#define fi first
#define se second
#define ot(x) cout<<x<<'
';
#define maxn 10000+5
int A[maxn];
int n,t,x,y,a,b;
vector<int> v;
bool check(int l,int mid)
{
   v.clear();
   for(int i=1;i<=n;i++){
     if(i<l)v.push_back(A[i]);
     else if(i>mid)v.push_back(A[i]);
     else i=mid;
   }
   sort(v.begin(),v.end());
   int n=unique(v.begin(),v.end())-v.begin();
   return n==v.size();
}
signed main()
{
    sc(n);
    for(int i=1;i<=n;i++){
        sc(A[i]);
        v.push_back(A[i]);
    }
    sort(v.begin(),v.end());
    int x=unique(v.begin(),v.end())-v.begin();
 
    if(x==n){
        cout<<0<<'
';
        return 0;
    }
    int len=n;
    for(int i=1;i<=n;i++){
        int l=i,r=i+len-1;
        if(!check(i,r))continue;
        while(l+1<r){
            int mid=(l+r)/2;
            if(check(i,mid)){
                r=mid;
            }else l=mid+1;
        }
        if(check(i,l)){
            len=min(l-i+1,len);
        }else if(check(i,r)){
            len=min(r-i+1,len);
        }
    }
    cout<<len<<'
';
}
原文地址:https://www.cnblogs.com/liulex/p/11411202.html