NC200630. 小阳排队
描述
输入描述
第一行 输入一个t，代表数据组数(1<=t<=10)
第二行 输入一个n，代表n个人在这里排队（1<=n<=500000）
第三行 这一行n个数，是n个数的排列，代表每个人的身高
输出描述
有t行，每行一个数，代表最小的操作次数使它有序
示例1
输入:
2 5 1 3 5 2 4 3 2 3 1
输出:
3 1
C++14(g++5.4) 解法, 执行用时: 1752ms, 内存消耗: 6760K, 提交时间: 2020-04-11 16:45:13
#include<bits/stdc++.h>
using namespace std;
int sz[500005];
int dp[500005];
int main()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
dp[i]=0;
cin>>sz[i];
}
int maxn=0;
for(int i=1;i<=n;i++)
{
dp[sz[i]]=dp[sz[i]-1]+1;
if(dp[sz[i]]>maxn)maxn=dp[sz[i]];
}
cout<<n-maxn<<endl;
}
}
C++11(clang++ 3.9) 解法, 执行用时: 570ms, 内存消耗: 35456K, 提交时间: 2020-07-09 14:37:59
#include<bits/stdc++.h>
using namespace std;
int V[500005];
int main()
{
int i,n,x,ans,T;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
ans=0,memset(V,0,sizeof(V));
for(i=0;i<n;i++)
{
scanf("%d",&x);
V[x]=V[x-1]+1,ans=max(ans,V[x]);
}
printf("%d\n",n-ans);
}
return 0;
}