慕容琳的后花园
慕容琳的后花园
洛谷#CF1223D#Sequence Sorting

Sequence Sorting

有n个数的序列,每次操作可以选择一种数,将他们全部移到开头或结尾:

1,5,2,1,3,2 -> 1,1,5,2,3,2(选1)

1,5,2,1,3,2 -> 5,2,3,2,1,1(选1)

问最少需要多少次操作,才能使序列变为非递减序列。

解法

显然最多的操作次数就是数的种数

那怎么节省操作次数呢

考虑有些数不用动,而不用动的这些数会构成一个

离散化之后值连续的不下降子序列

那么我们求出最长的值连续的不下降子序列即可

ac代码

#include<bits/stdc++.h>
#define N 300010
using namespace std;
int T,n,cnt,x,ans,a[N],first[N],last[N],f[N];
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n),ans=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            if(!first[a[i]])
                first[a[i]]=i;
            last[a[i]]=i;
        }
        sort(a+1,a+n+1);
        cnt=unique(a+1,a+n+1)-a-1;
        for(int i=1;i<=cnt;i++)
        {
            if(first[a[i]]>last[a[i-1]])
                f[a[i]]=f[a[i-1]]+1;
            else f[a[i]]=1;
            ans=max(ans,f[a[i]]);
        }
        printf("%d\n",cnt-ans);
        for(int i=1;i<=cnt;i++)
            first[a[i]]=f[a[i]]=0;
    }
    return 0;
}
赞赏
首页      洛谷      洛谷#CF1223D#Sequence Sorting
https://secure.gravatar.com/avatar/8cbc0c58deea66b18e9a96cd4bdd6eea?s=256&d=monsterid&r=g

慕容琳

文章作者

发表评论

textsms
account_circle
email

慕容琳的后花园

洛谷#CF1223D#Sequence Sorting
Sequence Sorting 有n个数的序列,每次操作可以选择一种数,将他们全部移到开头或结尾: 1,5,2,1,3,2 -> 1,1,5,2,3,2(选1) 1,5,2,1,3,2 -> 5,2,3,2,1,1(选1) 问最少需要多少次操…
扫描二维码继续阅读
2019-11-03
功能