HDU 2017 多校联赛5 1011 Rikka with Competition
Problem Description
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. n players will take part in it. The ith player’s strength point is ai.
If there is a match between the ith player plays and the jth player, the result will be related to |ai−aj|. If |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−1 matches, the last player will be the winner.
Now, Yuta shows the numbers n,K and the array a 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), the number of the testcases. And there are no more than 2 testcases with n>1000.
For each testcase, the first line contains two numbers n,K(1<=n<=105,0<=K<109).
The second line contains n numbers 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
题目大意：
摔跤比赛将于明天举行。运动员将参加。随着玩家的实力是AI。
如果有与玩家之间，金天海球员比赛，结果将是| AI−AJ |相关。如果| AI−AJ |＞K，与高强度点的玩家将赢得。否则，每个玩家将有机会赢得。
比赛的规则有点奇怪。每一次，裁判都会随机从剩下的球员中选出两名球员，并在他们之间进行比赛。失败者将被淘汰。N−1场比赛后，最后的球员将是赢家。
现在，Yuta显示数N、K和阵列，他想知道有多少玩家有机会赢得比赛。
把 a_ia
i
从大到小排序，那么第 ii 强人要获胜，最优情况下是最强的人输给了第二强的人，第二强的人输给了第三强的人，以此类推。因此只需要判断排序后 max_{j
c++
#include <bits/stdc++.h>
using namespace std;
int main()
{
int N;
cin>>N;
while(N--)
{
int n,k;
int a[500001];
cin>>n>>k;
for (int i=0; i<n; i++)
{
cin>>a[i];
}
sort(a,a+n);
int ans=0;
int flag=0;
for (int i=n-1; i>0; i--)
{
if (abs(a[i]-a[i-1])<=k)
{
ans += 1;
//cout<<"!!!!"<<endl;
}
else
{
ans += 1;
flag=1;
break;
}
}
if (abs(a[0]-a[1])<=k&&flag==0)
ans++;
cout<<ans<<endl;
}
}
凡岛公司福利 381人发布