HDU 6095 Rikka with Competition(水~)

xiaoxiao2021-02-28  35

Description

n 个人比赛,第i个人的能力值是 ai i j比赛,如果 |aiaj|K 则两人均由机会赢,否则能力值高的人赢,每次随机选两个人比赛,输的淘汰, n1 场比赛后赢者即为冠军,问有多少人有几率得到冠军

Input

第一行一整数 T 表示用例组数,每组用例首先输入两个整数n,K,之后输入 n 个整数ai表示每个人的能力值 (1T100,1n105,0K<109)

Output

输出有几率得到冠军的人数

Sample Input

2 5 3 1 5 9 6 3 5 2 1 5 9 6 3

Sample Output

5 1

Solution

ai 升序排序,如果要能力值第 k 强的人获胜,那么最强的人要输给第二强的人,第二强的人要输给第三强的人,以此类推知a1a2,a2a3,...,ak1akK,从前往后扫一直到该条件不满足时,前面的人均由可能当冠军,后面的人没有可能当冠军

Code

#include<cstdio> #include<algorithm> using namespace std; namespace fastIO { #define BUF_SIZE 100000 //fread -> read bool IOerror=0; inline char nc() { static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE; if(p1==pend) { p1=buf; pend=buf+fread(buf,1,BUF_SIZE,stdin); if(pend==p1) { IOerror=1; return -1; } } return *p1++; } inline bool blank(char ch) { return ch==' '||ch=='\n'||ch=='\r'||ch=='\t'; } inline void read(int &x) { char ch; while(blank(ch=nc())); if(IOerror)return; for(x=ch-'0';(ch=nc())>='0'&&ch<='9';x=x*10+ch-'0'); } inline void readc(char &x) { char ch; while(blank(ch=nc())); if(IOerror)return; x=ch; } #undef BUF_SIZE }; using namespace fastIO; #define maxn 100001 int T,n,k,a[maxn]; int main() { read(T); //scanf("%d",&T); while(T--) { read(n),read(k); //scanf("%d%d",&n,&k); for(int i=0;i<n;i++)read(a[i]);//scanf("%d",&a[i]); sort(a,a+n); int ans=1; for(int i=n-2;i>=0;i--) if(a[i+1]-a[i]<=k)ans++; else break; printf("%d\n",ans); } return 0; }
转载请注明原文地址: https://www.6miu.com/read-250075.html

最新回复(0)