P11522 [THUPC 2025 初赛] Harmful Machine Learning

题目背景

人工智能领域大神 The NIT 正在训练机器人 The BOT。

题目描述

The BOT 在一个 $1\times n$ 的网格上移动，其中在 $(1,i)$ 上有数字 $a_i$。The BOT 初始在格子 $(1,x)$, The BOT 想要走到一个数字尽量大的格子。每一步 The BOT 可以选择移动到相邻的一个格子或是不动，并且在移动后可以选择是否选择格子上的数字并结束游戏，而为了训练 The BOT 的能力，The NIT 会给出一些阻碍，在 The BOT 选择是否结束之后，The NIT 可以将两个数字交换位置。

具体地说，我们可以把整个游戏看成若干个回合，初始 The BOT 在位置 $(1,x)$，在一个回合中，以下事件会按顺序依次发生：

1. The NIT 选择两个位置 $1\le i,j\le n$，并交换 $a_i,a_j$ 的值，注意 $i$ 可以等于 $j$，此时交换不会带来任何变化。
2. The BOT 选择移动到一个相邻的位置或是原地不动，令 The BOT 现在所在的位置为 $y$，即选择 $1\le z\le n$ 且 $|z-y|\le 1$，并移动到 $(1,z)$。
3. The BOT 选择是否结束游戏，令 The BOT 现在所在的位置为 $y$，如果选择结束则会获得 $a_y$ 的分数并立刻结束游戏，否则无事发生。

可以发现，如果 The BOT 一直不选择结束游戏，则游戏永远不会结束，为了防止这个情况的发生，在游戏的第 $10^{114514}$ 个回合，The BOT 必须选择立刻结束游戏。

The NIT 希望 The BOT 结束游戏时的分数最小，而 The BOT 希望这个分数最大。The NIT 和 The BOT 都是绝顶聪明的，但他们并没有时间玩 $10^{114514}$ 个回合，于是他们请你帮他们计算一下，The BOT 最终的分数是多少？

输入格式

本题含有多组测试数据。

第一行一个整数 $T(1\le T\le 10^5)$，表示测试数据数量。

对于每一组数据：

第一行两个正整数 $n,x(1\le n\le 10^5,1\le x\le n)$，分别表示网格的长度以及初始位置 $(1,x)$。

之后一行 $n$ 个非负整数 $a_i(0\le a_i\le 10^9)$。

保证所有数据的 $n$ 的总和不超过 $5\times 10^5$。

输出格式

对于每一组数据，输出一行一个数表示答案。

输入输出样例 #1

输入 #1

4
3 2
1 2 3
13 4
1 1 4 5 1 4 1 9 1 9 8 1 0
4 2
1 10 100 1000
1 1
114514

输出 #1

3
4
100
114514

说明/提示

题目来源

题目来自 THUPC2025（2025年清华大学学生程序设计竞赛暨高校邀请赛）初赛，信息来源于 THUSAAC 仓库。

C++实现

#include<bits/stdc++.h>
using namespace std;
int t,n,x;
void solve(){
	cin>>n>>x;
	vector<int>a(n+1),b;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=x-1;i<=x+1;i++){
		if(1<=i&&i<=n)b.push_back(a[i]);
		else b.push_back(0);
	}
	sort(a.begin()+1,a.end());
	sort(b.begin(),b.end());
	if(n<=2)cout<<a[n]<<"\n";
	else cout<<max(a[3],b[1])<<"\n";
	return;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>t;
	while(t--){
		solve();
	}
	return 0;
} 

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容