题目题解

问题理解

有 $n$ 名选手，第 $i$ 名选手的实力为 $a_i$。
游戏进行直到剩余人数 $\le k$ 为止。每轮随机选择两名剩余选手，淘汰实力较低者（若相等则随机淘汰一人）。
给定 $j$ 和 $k$，问选手 $j$ 是否有可能成为最后 $k$ 名选手之一。

第一步：$k > 1$ 的情况

结论：若 $k > 1$，则答案总是 "YES"。

原因：
选手 $j$ 可能在整个游戏过程中从未被选中。
由于每次只淘汰两人中的一人，且随机选择对手，只要 $j$ 始终不被选中，他就可以一直存活到最后。
当剩余人数恰好为 $k$ 时，游戏结束，$j$ 自然在其中。
因此，对于 $k > 1$，无论如何选手 $j$ 都有可能进入最后 $k$ 人。

第二步：$k = 1$ 的情况

结论：答案为 "YES" 当且仅当选手 $j$ 的实力是最大值。

原因：
考虑所有实力最大的选手集合。
由于每轮淘汰的是实力较低者，实力最大者永远不会被淘汰（因为不存在实力比他高的人，且平局时随机淘汰，但至少有一个最大实力者会存活）。
因此，最后剩下的唯一一人必定是某个实力最大者。
若选手 $j$ 的实力不是最大值，则他不可能成为最后一人。

最终算法

对于每个测试用例：

1. 读入 $n, j, k$ 和数组 $a_1, \dots, a_n$。
2. 若 $k > 1$，输出 "YES"。
3. 否则（$k = 1$），输出 "YES" 当且仅当 $a_j = \max(a_1, \dots, a_n)$。

时间复杂度

• 每个测试用例 $O(n)$ 时间。
• 总复杂度 $O(\sum n) \le 2 \times 10^5$，满足要求。

代码实现

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n, j, k;
    cin >> n >> j >> k;
    vector<int> a(n + 1);
    int mx = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        mx = max(mx, a[i]);
    }
    
    if (k > 1) {
        cout << "YES\n";
    } else {
        cout << (a[j] == mx ? "YES" : "NO") << '\n';
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    
    return 0;
}

验证样例

与题目输出一致。

总结

本题的关键在于：

1. 当 $k > 1$ 时，选手 $j$ 可以通过一直不被选中而存活。
2. 当 $k = 1$ 时，只有实力最强的选手才能成为最后一人。
3. 因此，答案只取决于 $k$ 是否大于 $1$ 以及选手 $j$ 是否拥有最大实力。