hiho1523 数组重排2

时间限制:10000ms

单点时限:1000ms

内存限制:256MB

描述

给定一个1-N的排列A1, A2, ... AN，每次操作小Hi可以选择一个数，把它放到数组的最左边。

请计算小Hi最少进行几次操作就能使得新数组是递增排列的。

输入

第一行包含一个整数N。

第二行包含N个两两不同整数A1, A2, ... AN。(1 <= Ai <= N)

对于60%的数据 1 <= N <= 20

对于100%的数据 1 <= N <= 100000

输出

一个整数代表答案

样例输入

5

2 3 1 4 5

样例输出

其实按照汉诺塔的思路去推，很容易得出结论： 倒序统计 n n-1 n-2...的延伸长度能得到最大不需要移动个数。

比如：1-3-4-5-2，3-4-5可以不移动

#include<cstdio>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#include<memory>

#include<cstring>

using namespace std;

int a[],ans,now;

int main()

{

    int i,j,n;

    scanf("%d",&n);

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

    now=n;

    for(i=n;i>=;i--){

        if(a[i]==now){

            ans++;

            now--;

        }

    }

    printf("%d\n",n-ans);

    return ;

}

巴特西

hiho1523 数组重排2

描述

输入

输出

最新文章

热门文章