题目描述

难度分:$1200$

输入$T(\leq 2 \times 10^4)$表示$T$组数据。所有数据的$n$之和$\leq 2 \times 10^5$。

每组数据输入$n(2 \leq n \leq 10^5)$和长为$n$的数组$a(1 \leq a[i] \leq 10^9)$，下标从$1$ 开始。

Alice和Bob玩回合制游戏，Alice先。

每回合，如果$a_1=0$，那么当前玩家输掉游戏，对手获胜。

否则当前玩家把$a_1$减少一，然后选择一个下标在$[2,n]$中的数字和$a_1$交换。

双方都以最佳方式游戏，输出最后谁赢了。

输入样例

3
2
1 1
2
2 1
3
5 4 4

输出样例

Bob
Alice
Alice

算法

贪心

思维题，只要Alice保证自己操作的不是最小值，那么每次他都可以操作完后把最小值换到前面来给Bob操作，这样一来Bob每次都是操作的最小值，无论他换哪个数到前面来让Alice操作，Bob都一直在减少最小值，所以必然是他面对将$a[1]$减成$0$的局面，Alice此时必胜。

复杂度分析

时间复杂度

只遍历了一遍数组，检查$a[1]$是不是大于$min_{i=2}^{n}a[i]$即可，大于就是Alice赢，否则是Bob赢。因此，算法的时间复杂度为$O(n)$。

空间复杂度

除了输入的$a$数组之外，只使用了有限几个变量，额外空间复杂度为$O(1)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 200010;
int T, n, a[N];

int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        int a1 = 0, mn = 0;
        for(int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
            if(i == 1) {
                a1 = a[i];
            }else {
                if(mn == 0) mn = a[i];
                else mn = min(mn, a[i]);
            }
        }
        if(a[1] > mn) {
            puts("Alice");
        }else {
            puts("Bob");
        }
    }
    return 0;
}