首页 > 其他 > 详细

洛谷#CF1223D#Sequence Sorting

时间:2019-11-03 13:53:29      阅读:64      评论:0      收藏:0      [点我收藏+]

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://www.cnblogs.com/muronglin/p/luogu-cf1223d.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!