问题 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] ,表示玩家的能力值。

输出

一个整数,表示最后可能获胜的玩家个数。

样例输入
Copy
5 3
1 5 9 6 3
样例输出
Copy
5

提示

数据规模
共 10 组数据。
测试点 1 满足 n ≤ 5。
测试点 2 满足 n≤ 10。
测试点 3,4,5 满足 n≤ 1000。
对于 100% 的数据,满足 n≤10^5, 1≤a[i],K≤10^9。

来源

[提交][状态]