CF2123B.Tournament

入门

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定一个整数数组 $ a_1, a_2, \dots, a_n $。一场淘汰赛在 $ n $ 名玩家中进行。玩家 $ i $ 拥有实力值 $ a_i $。

当剩余的玩家数量大于 $ k $ 时，重复以下过程：

随机选择两名剩余的玩家；
然后，实力值较低的玩家被淘汰。如果两名被选择的玩家实力值相同，则随机淘汰其中一人。

给定整数 $ j $ 和 $ k $（$ 1 \leq j, k \leq n $），判断玩家 $ j $ 是否有可能成为最后剩下的 $ k $ 名玩家之一。

输入格式

第一行包含一个整数 $ t $（$ 1 \leq t \leq 10^4 $）—— 测试用例的数量。

每个测试用例的第一行包含三个整数 $ n $、$ j $ 和 $ k $（$ 2 \leq n \leq 2\cdot 10^5 $，$ 1 \leq j, k \leq n $）。

每个测试用例的第二行包含 $ n $ 个整数 $ a_1, a_2, \dots, a_n $（$ 1 \leq a_i \leq n $）。

保证所有测试用例的 $ n $ 的总和不超过 $ 2\cdot 10^5 $。

输出格式

对于每个测试用例，如果玩家 $ j $ 有可能成为最后剩下的 $ k $ 名玩家之一，则在单独一行输出 "YES"，否则输出 "NO"。

你可以输出答案的任意大小写形式（大写或小写）。例如，字符串 "yEs"、"yes"、"Yes" 和 "YES" 都将被视为肯定回答。

输入输出样例

输入#1

3
5 2 3
3 2 4 4 1
5 4 1
5 3 4 5 2
6 1 1
1 2 3 4 5 6

输出#1

YES
YES
NO

说明/提示

在第一个样例中，假设首先选择玩家 $ 2 $（实力值 $ 2 $）和玩家 $ 5 $（实力值 $ 1 $）。那么玩家 $ 2 $ 淘汰玩家 $ 5 $。现在，剩余的玩家实力值为 $ [3, 2, 4, 4] $（对应玩家 $ 1, 2, 3, 4$）。接着，假设选择玩家 $ 3 $（实力值 $ 4 $）和玩家 $ 4 $（实力值 $ 4 $）。那么玩家 $ 3 $ 可能淘汰玩家 $ 4 $（或反之）。现在，剩余的玩家实力值为 $ [3, 2, 4] $（对应玩家 $ 1, 2, 3$）。玩家 $ 2 $ 是最后剩下的三名玩家之一。

在第三个样例中，可以证明玩家 $ 1 $ 绝无可能成为最后剩下的那名玩家。

翻译由 DeepSeek R1 完成。

输入解题思路，AI测评打分。不知道怎么写?

首页