题解：P11522 [THUPC2025 初赛] Harmful Machine Learning
有人代码长，有人常数大，而我两个都占。
赛时全队花费 2h+ 的时间才写出的题。
思路
分类讨论。
-
当
n \le 3 时，容易想到，此时的答案就是a_i 的最大值。 -
当
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 只能停在两个位置，考虑两种情况。
-
能停在的格子是序列中的次小值和最小值。此时 NIT 不动，模拟易得，最大分数即为除能达到的的两个数外的数中最小的那个（即所有数中第三小的那个）。
-
否则，可以直接一轮结束游戏，也可以向中间走一格，转化为
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;
}