自动搬运

查看原文

来自洛谷，原作者为

	ARIS1_0 我们在逆境中绽放||go whk 8.24-9.30

搬运于2025-08-24 23:05:11，当前版本为作者最后更新于2024-10-17 08:23:18，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

十分简单的贪心题。

利用贪心思想，对所有人的身高从小到大进行排序。随后将相邻的两个元素划分进一组进行比较，若不符合条件，直接输出 No，若符合则选择下两个相邻的元素并重复上述流程。

为什么这是对的？设比较之后的数组为 $A$，$D$ 为容许的身高误差。显然有 $A_1 \le A_2 \le A_3 \le \dots \le A_{2\times n-1} \le A_{2\times n}$。若有 $A_{i+2}-A_i \le D$，则必有 $A_{i+1}-A_i\le D$，但是如果将 $(A_{i+2},A_i)$ 配对，那么剩下的 $A_{i+1}$ 就需要去和身高更高或更矮的学生进行配对，那么此时可能得到的身高误差就一定不会小于用 $A_{i+2}$ 去配对更高的学生得到的身高误差或者用 $A_{i-1}$ 去配对更矮的学生得到的身高误差。为了满足题目的条件，我们必须将每一组学生的身高误差都尽可能缩小，故将 $(A_{i+1},A_i)$ 配对是优于将 $(A_{i+2},A_i)$ 配对的。

不符合条件的情况也很显然。注意到 $A_{i+1}-A_i > D$，那么一定有 $A_{i+2}-A_i>D$，所以此时无解。

代码就不放了，个人觉得讲的还算清晰。