1592.死亡之组

时间限制:1s 内存限制:256MB

有 $n$ 个队伍参与了世界杯,编号为 $1,2,…,n$。第 $i$ 号队伍实力用一个整数 $a_i$ 描述。

现在所有队伍被划分为若干小组,每个小组由四个队伍构成,每个队伍恰好属于一个小组。

我们称一个小组是“死亡之组”,当其至少符合以下条件之一:

  • 小组中存在多个球队的实力都相当出色,有至少两支队伍的实力不小于 $L$。

  • 四支球队水平极其接近,小组中最高实力队伍和最低实力队伍的实力之差不超过 $D$。

现在假设你可以决定分组,问是否存在一种分组方案,使得 $1$ 号队伍所在的组不是“死亡之组”。

输入格式(从终端/标准输入读取)

第一行一个整数 $t (1≤t≤20)$,代表数据组数。

对于每组数据:

  • 第一行 $3$ 个整数 $n,L,D (1≤n≤10^5,1≤L,D≤10^9)$ ,保证 $n$ 是 $4$ 的倍数。

  • 第二行 $n$ 个整数 $a_1,a_2,…,a_n (1≤a_i≤10^9)$,代表 $n$ 个队伍的实力。

输出格式(输出至终端/标准输出)

对于每组数据输出一行,如果可以构造出一种符合要求的方案,输出 Yes,否则输出 No

输入样例

复制
1
8 6 4
1 2 3 4 5 6 7 8
 \n
 · · \n
 · · · · · · · \n

输出样例

复制
Yes
   \n

说明

可以选择 $1,3,5,7$ 组成一个小组。

来源: 2024“钉耙编程”中国大学生算法设计超级联赛(3)

提交题解

Please login first.

© 2025 FAQs