数列 A 包含 n 个正整数,且没有相同的数,小明的目标是删除最大和最小的数。但他每次只能从剩余数列的最左边的数,或者最右边的数。请计算小明最少需要删除几个数,才能达成目标(即删除最大和最小的数)。
例如,n=5,A=[1,8,5,4,3],小明依次操作为: 删除最左边的数,得到 A=[8,5,4,3]; 删除最右边的数,得到 A=[8,5,4]; 删除最左边的数,得到 A=[5,4],至此他把最大数 8 和最小数 1 都删除了,目标达成。
而实际上,上面的例子可以只用2步达成目标: 删除最左边的数,得到 A=[8,5,4,3]; 删除最左边的数,得到 A=[5,4,3],目标达成。
第一行一个整数 t 表示数据的组数。(1<=t<=100) 接下来 t 组输入,每组两行,第一行一个正整数 n 表示初始数列大小;(2<=n<=100) 第二行包含 n 个互不相同的正整数 A1,A2,...,An(1<=Ai<=n),表示数列。
一共 t 行,每行表示一组数据的答案,即最少删除几个数能达成目标。
5
5
1 5 4 3 2
8
2 1 3 4 5 6 8 7
8
4 2 3 1 8 6 7 5
4
3 4 2 1
4
2 3 1 4
2
4
5
3
2
小小dfs我竟然没做对,求大佬指教,问题解决蒟蒻定感激不尽+关注
这是我的代码(码风丑陋请见谅):
#include<bits/stdc++.h>
using namespace std;
int T,n,a[210],ans=2e9,wzx,wzn,maxn,minn=2e9;
bool vis[210];
void dfs(int l,int r,int step){
if(vis[wzx]&&vis[wzn]){
ans=min(ans,step);
return;
}
for(int i=1;i<=2;i++){
if(i==1&&!vis[l]){
vis[l]=true;
dfs(l+1,r,step+1);
vis[l]=false;
}
if(i==2&&!vis[r]){
vis[r]=true;
dfs(l,r-1,step+1);
vis[r]=false;
}
}
}
int main()
{
cin>>T;
while(T--){
cin>>n;
wzx=1;
wzn=n;
for(int i=1;i<=n;i++) {
cin>>a[i];
if(maxn>a[i]){
maxn=a[i];
wzx=i;
}
}
for(int i=n;i>=1;i--){
if(wzx!=i&&minn<a[i]){
minn=a[i];
wzn=i;
}
}
ans=2e9;
dfs(1,n,0);
cout<<ans<<endl;
}
return 0;
}
样例都输出 2