求助一道站外题
  • 板块学术版
  • 楼主Fearliciz
  • 当前回复10
  • 已保存回复10
  • 发布时间2021/10/2 21:15
  • 上次更新2023/11/4 05:06:14
查看原帖
求助一道站外题
326452
Fearliciz楼主2021/10/2 21:15

题目描述:

数列 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

2021/10/2 21:15
加载中...