U586024 锦标赛(tournament)
题目描述
有 $n$ 个玩家参加比赛,他们分别有能力值 $a_1, a_2, ..., a_n$ 。
需要进行 $n-1$ 轮比赛,每一轮在剩下的玩家里任选两个玩家对决。对决规则如下:
- 如果 $|a_i - a_j| > K$ ,那么能力值高的玩家获胜,能力值低的玩家被淘汰。
- 如果 $|a_i - a_j| \leq K$ ,则两个玩家都有可能获胜,另一个玩家被淘汰。
经过 $n-1$ 轮比赛后,只剩下一个玩家。问有多少个玩家可能成为最后的获胜者。
输入格式
第一行包含两个整数 $n$ 和 $K$,分别表示玩家的总人数和获胜条件中的参数。
第二行包含 $n$ 个整数 $a_1, a_2, ..., a_n$,表示每个玩家的能力值。
输出格式
输出一个整数,表示可能成为最后获胜者的玩家数量。
说明/提示
- 注意考虑 $K = 0$ 的特殊情况。
- 玩家能力值可能相同。
- 使用排序和滑动窗口的方法可以有效解决问题。