CUC-SUMMER-CONTEST-2-H

H - Rikka with Competition

HDU - 6095

As we know, Rikka is poor at math. Yuta is worrying about this situation, so he gives Rikka some math tasks to practice. There is one of them:

A wrestling match will be held tomorrow. nn players will take part in it. The iith player’s strength point is aiai.

If there is a match between the iith player plays and the jjth player, the result will be related to |ai−aj||ai−aj|. If |ai−aj|>K|ai−aj|>K, the player with the higher strength point will win. Otherwise each player will have a chance to win.

The competition rules is a little strange. Each time, the referee will choose two players from all remaining players randomly and hold a match between them. The loser will be be eliminated. After n−1n−1 matches, the last player will be the winner.

Now, Yuta shows the numbers n,Kn,K and the array aa and he wants to know how many players have a chance to win the competition.

It is too difficult for Rikka. Can you help her?
Input
The first line contains a number t(1≤t≤100)t(1≤t≤100), the number of the testcases. And there are no more than 22 testcases with n>1000n>1000.

For each testcase, the first line contains two numbers n,K(1≤n≤105,0≤K<109)n,K(1≤n≤105,0≤K<109).

The second line contains nn numbers ai(1≤ai≤109)ai(1≤ai≤109).
Output
For each testcase, print a single line with a single number -- the answer.
Sample Input
2
5 3
1 5 9 6 3
5 2
1 5 9 6 3
Sample Output
5
1

题意：很多人参加一个比赛，如果两个人的实力差距不超过k，那么两个人都有可能赢，给你选手的实力值，判断有几个人可能得到冠军

解法：将实力值排序，设置计数器，如果从小到大，如果两个相邻数的差小于等于k，计数器加一，否则计数器归零，最终计数器的值为答案

代码：

#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=100000+10;
int a[maxn];
int main()
{
    int num,n,k,flag;
    cin>>num;
    while(num--){
        flag=0;
        cin>>n>>k;
        for(int i=0;i<n;i++)
            cin>>a[i];
        sort(a,a+n);
        for(int i=1;i<n;i++){
            if(a[i]-a[i-1]>k){
                flag=i;
            }
        }
        cout<<n-flag<<endl;
    }
}