C. Swap Game（简单博弈）

题目

题意

给定n个数a1,a2,…,an，Alice和Bob轮流从执行以下操作

• 将数a1减1，
• 从a2到an中，任意选择一个元素，与a1交换。

如果轮到的选手，当前的a1是0，则输掉比赛。
Alice先执行操作。

问，如果Alice和Bob都采取最明智的策略，谁最终会赢。

1<=a1<=n

思路

题目的关键，是谁拿到了0，谁就输。

那么显然，我们在替换元素时，必定选择a2到an中，最小的元素给对方，并在之后的操作继续选择这个元素。这样，能确保最快让对方选到0。

利用上述策略，Alice可以选择a2到an中最小的元素。
Bob没有选择优势，只能看他手头原始的a1元素。

• 如果a1<=min(a2,…,an)，那么Bob必胜，他只要后边都选择a1这个元素去减，必能先于Alice走到0。
• 如果a1>min(a2,…,an)，那么此时Alice必胜，此时必胜的元素存在于a2,a3,…,an中，而Alice有优先选择权利。

代码

#include 
using namespace std;
#define ll long long
const int maxn = 200010;

int n, k;
int x, y, mn;
void solve() {
	scanf("%d", &n);
	scanf("%d", &x);
	mn = 1000000000;
	for (int i = 1; i < n; ++i) {
		scanf("%d", &y);
		mn = min(mn, y);
	}
	printf("%s\n", x <= mn ? "Bob" : "Alice");
}
int main() {
	int t;
	scanf("%d", &t);
	while (t--) {
		solve();
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24