zcmimi's blog
avatar
zc
2019-12-21 19:47:00
  • 本文总阅读量
查看原题

点击跳转

#include<bits/stdc++.h>
using namespace std;
int n,c[1000005],ans[1000005],m,ansl;
vector<int>a[1000005];
int cun[1000005],tot;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>c[i],a[c[i]].push_back(i),m=max(m,c[i]);
    for(int i=1;i<=m;i++)
        if(a[i].size()!=0)cun[++tot]=i;
    for(int i=1;i<=tot;i++){
        int now=cun[i],last=cun[i-1],nxt=cun[i+1];
        ans[i]=a[now].size();
        if(i!=1)
            if(a[now].front()>a[last].back())ans[i]+=ans[i-1];
            else{
                int aa=lower_bound(a[last].begin(),a[last].end(),a[now].front())-a[last].begin();
                ans[i]+=aa;
            }
        if(i!=tot)
            if(a[now].back()>a[nxt].front()){
                int aa=lower_bound(a[nxt].begin(),a[nxt].end(),a[now].back())-a[nxt].begin();
                ans[i]+=(a[nxt].size()-aa);
            }
        ansl=max(ansl,ans[i]);
    }
    cout<<n-ansl<<endl;
}
LG 3411 序列变换
comment评论
Search
search