自动搬运

查看原文

来自洛谷，原作者为

	MassPoint 我要蓝钩

搬运于2025-08-24 23:08:04，当前版本为作者最后更新于2025-01-08 23:04:16，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

赛时全队花费 2h+ 的时间才写出的题。

思路

分类讨论。

1. 当 $n \le 3$ 时，容易想到，此时的答案就是 $a_i$ 的最大值。

2. 当 $n > 3$时，考虑$1 < x < n$ 和 $x=1$ 或者 $x=n$ 两种情况。

当 $1 < x < n$ 时

首先，要使分数最小，NIT 一定会把 BOT 走不到的格子中最小的那个格子和 BOT 能走到的最大的格子交换（如果 BOT 能走到的格子本身就是最小的那几个，可以看作不交换），让 BOT 只能选移动前三个格子中的次大值。

而且，BOT 每移动一次，NIT 都能将它周围的格子换成较小的格子，并把每次往自己周围次大格移动的 BOT 控制在两个格子之内。BOT 和 NIT 玩的回合数越多，局势对 BOT 越不利。

因此，在该情况下，BOT 只玩一个回合是最有利的。

当 $x = 1$ 或 $x = n$ 时

此时开局，BOT 只能停在两个位置，考虑两种情况。

1. 能停在的格子是序列中的次小值和最小值。此时 NIT 不动，模拟易得，最大分数即为除能达到的的两个数外的数中最小的那个（即所有数中第三小的那个）。

2. 否则，可以直接一轮结束游戏，也可以向中间走一格，转化为 $1 < x < n$ 的情况。答案即为这两种情况得出的分数的最大值。

代码

#include<bits/stdc++.h>
using namespace std;
int t,n,x;
int a[100001]; 
int cmp(int a,int b){
	return a<=b;
}
int main(){
	scanf("%d",&t);
	a[0]=1e9;
	while(t--){
		scanf("%d%d",&n,&x);
		for(int i=1;i<=n;i++)	scanf("%d",&a[i]);
		if(n<=3){
			int mx=0;
			for(int i=1;i<=n;i++){
				mx=max(mx,a[i]);
			}
			printf("%d\n",mx);
			continue;
		}
		if(x==n){	//当 x=n 时，将数列翻转，转化为 x=1 的情况。
			x=1;
			for(int i=1;i<=n/2;i++){
				swap(a[i],a[n-i+1]);
			}
		}
		if(x==1){	//当 x=1，BOT 要努力走到中间。 
			int res;
			int fl=1e9,op;
			for(int i=3;i<=n;i++){	//找到 BOT 这一回合不能抵达的格子中数字最小的那个格子。
				if(a[i]<fl) op=i; 
				fl=min(fl,a[i]);
			}
			if(fl<a[1]||fl<a[2]){	//按照 NIT 的策略，把 a[1] 和 a[2]中的最大值与序列中 BOT 到不了的地方的最小值交换。
				res=min(a[1],a[2]);	//直接一轮结束游戏，取最小值是因为能够到的最大值被 NIT 交换走了。
				if(a[2]>a[1])
					swap(a[2],a[op]);
				else
					swap(a[1],a[op]);
			}
			else{	//说明 a[1] 和 a[2] 分别是序列中的最小值和次小值，此时 BOT 顶多只能拿到 fl 点分数，直接特判。
				printf("%d\n",fl);
				continue;
			}
			x++;	//否则向中心移动，花费两轮结束游戏。
			int mi=x-1,mx=x+1;
			sort(a+mi,a+mx+1,cmp);	//由于 BOT 周围够得到的格子的位置关系其实不影响游戏结果，所以可以直接排序。
			fl=0;
			for(int i=1;i<=n;i++){
				if(abs(i-x)<=1) continue;	//不把 BOT 能达到的格子算入。
				if(a[i]<=a[fl])	fl=i;
			}
			if(a[fl]<a[mx])	swap(a[mx],a[fl]);
			sort(a+mi,a+mx+1);
			res=max(res,a[mx]);	//取一轮结束与两轮结束答案的最大值。
			printf("%d\n",res);
			continue;
		}
		int mi=x-1,mx=x+1;
		sort(a+mi,a+mx+1,cmp);
		int fl=0;
		for(int i=1;i<=n;i++){
			if(abs(i-x)<=1) continue;
			if(a[i]<=a[fl])	fl=i;
		}
		if(a[fl]<a[mx])	swap(a[mx],a[fl]);	//NIT 进行交换。
		sort(a+mi,a+mx+1);
		printf("%d\n",a[mx]);	//交换完毕后，BOT 选择停在它周围数字最大的格子上，直接结束游戏。
	}
	return 0;
}