题解：P11199 [JOIG 2024 Open] ダンス / Dance

ARIS1_0 · 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，所以此时无解。

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