CF2123B Tournament

原题链接：B. Tournament

Tag：结论题

题目描述

给定一个整数数组 \(a_1,a_2,\dots,a_n\)。举行一场有 \(n\) 名玩家参与的锦标赛，第 \(i\) 名玩家的力量值为 \(a_i\)。

当剩余玩家数量大于 \(k\) 时，重复以下过程： - 随机选择两名剩余玩家； - 力量值较低的玩家被淘汰。如果两名玩家力量值相同，则随机淘汰其中一人。

给定整数 \(j\) 和 \(k\)，判断是否存在一种可能，使得玩家 \(j\) 成为最后剩下的 \(k\) 名玩家之一。

数据说明：

• \(1 \leq t \leq 10^4\)
• \(2 \leq n \leq 2 \cdot 10^5\)
• \(1 \leq j,k \leq n\)
• \(1 \leq a_i \leq n\)
• \(\sum n \leq 2 \cdot 10^5\)

分析

首先有一个显然的情况，如果 \(j\) 选手的数值本身就是最高的， 那么无论 \(k\) 如何，\(j\) 选手都可以留到后 \(k\) 个。

那么我们再思考一下 \(j\) 号选手分数不是最高的情况， 有没有可能是 \(j\) 号选手凭借运气一直活到后 \(k\) 个呢？

答案是肯定的，只要 \(k\) 不等于 \(1\)，\(j\) 选手就可以凭借一直不被选到活到最后 \(k\) 个。 如果 \(k=1\)，只有数值最大的选手能活到最后，\(j\) 选手如果能力不是最大的，那么被淘汰是必然的。

因此结论显然：要么 \(k\geq 2\)，要么 \(j\) 选手本身能力值就是最大的。

代码实现

void NeverSayNever() {
    int n, j, k; 
    cin >> n >> j >> k;
    vector<int> vec(n);
    for (auto &x: vec) cin >> x;
    int mx = *std::max_element(vec.begin(), vec.end());
    if (vec[j - 1] == mx || k >= 2) cout << "YES" << endl;
    else cout << "NO" << endl;
}

日志

本页面创建于 2025/7/4 23:06