1700 首尾排序法

有一个长度为n的数组 p1, p2, p3, ⋯, pnp1, p2, p3, ⋯, pn ，里面只包含1到n的整数，且每个数字都不一样。现在要对这个数组进行从小到大排序，排序的时候只能是把一个数字拿过来放到数组末尾或者开头，问最少要操作几次才能使得这个数组从小到大排序。

样例解释：

先把4移动到最后，然后再把5移动到后。

收起

输入

单组测试数据。

第一行一个整数n (1≤n≤100000)，表示数组的长度。

第二行有n个整数 pi (1≤pi≤n, 如果 i≠j，那么pi≠pj ) ，表示数组中的数字。

输出

输出一个整数，表示最少要操作几次才能使得数组从小到大有序。

输入样例

5

4 1 2 5 3

输出样例

思路：求一个最长的连续的子串(如样例中的1,2,3) 的长度len, 答案即为 n-len

代码如下：

#include<bits/stdc++.h>

using namespace std;

int a[100005];int n;

int par[100005];

bool vis[100005];

int dp[100005];

int len=0;

int dfs(int i)

{

    if(par[i]==i){dp[i]=1;return 1;}

    int p=par[i];

    if(dp[p]!=0){dp[i]=dp[p]+1;return dp[i];}

    return dfs(par[i]);

}

int main()

{

    //freopen("in.txt","r",stdin);

    scanf("%d",&n);

    for(int i=0;i<n;i++)scanf("%d",&a[i]);

    for(int i=1;i<=n;i++)par[i]=i;

    for(int i=0;i<n;i++)

    {

        if(vis[a[i]-1])

        {

            vis[a[i]-1]=0;par[a[i]]=a[i]-1;

            vis[a[i]]=1;

        }

        else vis[a[i]]=1;

    }

    for(int i=1;i<=n;i++)

    len=max(dfs(i),len);

    int ans=n-len;

    cout<<ans<<endl;

    return 0;

}

巴特西

51 Nod 1700 首尾排序法

1700 首尾排序法

输入

输出

输入样例

输出样例

最新文章

热门文章