内存:128  时间:1

题目描述

hcbbt巨巨,正宗GFS,深受万千学妹的爱慕,人们为了得到他的一张照片日思夜想,也没有个结果.如今,巨巨为了帮助无奈的霞姐,做出巨大牺牲.他出了一道思考题,凡是能够解出来的,可以获得巨巨的照片.

题意如下:有n个人,巨巨对这些人的身高进行编号,最 矮的为1,以此类推,最高的为n,我们保证每个人的身高都不一样,所以每个人的编号都是不一样的.现在打乱这n个人的顺序,问最少的移动次数使其编号从小 到大排序,移动的规则限定如下:每次只能把其中一个人放在第一个人的最前面,这样算一次操作.

输入

包含T组数据。每组数据第一行为一个整数n,代表有n个人

第二行是现在n个人的编号顺序(0<n<5000)

输出

每组数据输出一行,表示最小的移动次数使得序列从小到大排列。

样例输入

2
4
1 2 3 4
4
1 3 2 4

样例输出

0
2

提示

代码如下

#include <algorithm>
#include <iostream>
#include <sstream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <string>
#include <bitset>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <list>
#include <map>
#include <set>
using namespace std;
/***************************************/
typedef vector<int> VI;
typedef vector<char> VC;
typedef vector<string> VS;
typedef set<int> SI;
typedef set<string> SS;
typedef map<int ,int> MII;
typedef map<string,int> MSI;
typedef pair<int,int> PII;
typedef vector<PII> VII;
typedef vector<VI > VVI;
/***************************************/
#define clr(a,b) memset(a,b,sizeof(a))
#define all(x)	(x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define ll long long
#define int64 __int64
#define pb push_back
#define mp make_pair
#define LL(x) ((x)<<1)
#define RR(x) ((x)<<1|1)
#define ri(x) scanf("%d",&x)
#define rii(x,y) scanf("%d%d",&x,&y)
#define rd(x) scanf("%lf",&x)
#define rdd(x,y) scanf("%lf%lf",&x,&y)
#define rs(x) scanf("%s",x)
#define pi(x) printf("%d",x)
#define pin(x) printf("%d\n",x)
#define ps(x) printf("%s",x)
#define pn()  printf("\n")
#define sqr(x) ((x)*(x))
#define rep(i,a,b)  for(int i=(a);i<(b);i++)
#define repu(i,a,b) for(int i=(a);i<=(b);i++)
#define repd(i,a,b) for(int i=(a);i>=(b);i--)
#define repc(i,a,c) for(int i=(a);(c);i++)
/***************************************/
const int INF = 0x7f7f7f7f;
const double eps = 1e-8;
const double PIE=acos(-1.0);
const int dx[]= {0,-1,0,1};
const int dy[]= {1,0,-1,0};
const int fx[]= {-1,-1,-1,0,0,1,1,1};
const int fy[]= {-1,0,1,-1,1,-1,0,1};
/***************************************/
void openfile()
{
	freopen("data2.in","rb",stdin);
	freopen("data2.out","wb",stdout);
}
/**********************华丽丽的分割线,以上为模板部分*****************/

const int N = 300010;
int a[N],b[N];

int main()
{
    //openfile();
	int n,t;
	ri(t);
	while(t--)
	{
        ri(n);
		for(int i=0;i<n;i++)
		{
			ri(a[i]);
			b[i]=a[i];
		}
		sort(b,b+n);
		int cnt=0;
		for(int i=n-1,j=n-1;i>=0;i--)
		{
			if(a[i]==b[j])
			{
				j--;
				cnt++;
			}
		}
		printf("%d\n",n-cnt);
	}
	return 0;
}

代码来源于互联网,仅供参考!