问题 5311 --锦标赛(tournament)5311: 锦标赛(tournament)
时间限制: 1 Sec 内存限制: 128 MB
提交: 6 解决: 6
[提交][状态][命题人:]题目描述
有 n 个玩家参加比赛,他们分别有能力值 a[1],a[2],…,a[n] 。
需要进行 n−1 轮比赛,每一轮在剩下的玩家里任选两个玩家 i,j 。如果 |a[i]−a[j]|>K ,那么其中能力值高的玩家会获胜,能力值低的玩家会被淘汰。如果 |a[i]−a[j]|≤K ,那么两个玩家都有可能获胜,另一个玩家被淘汰。
n−1 轮比赛之后,只剩下一个玩家。问有多少个玩家可能是最后获胜的玩家。
输入
第一行,两个整数 n,K ,表示玩家的总人数,和获胜条件中的参数。
接下来一行 n 个整数 a[1],a[2],…,a[n] ,表示玩家的能力值。
输出
提示
数据规模
共 10 组数据。
测试点 1 满足 n ≤ 5。
测试点 2 满足 n≤ 10。
测试点 3,4,5 满足 n≤ 1000。
对于 100% 的数据,满足 n≤10^5, 1≤a[i],K≤10^9。
来源
[提交][状态]