C程序：巧用贪心算法解决舞会男女身高配对难题

要解决这个问题，我们可以采用贪心算法。具体步骤如下： 1. 读取输入：首先读取输入的 `n` 和 `d`，以及所有人的身高。 2. 排序：将所有人的身高进行排序。 3. 配对：从最矮的人开始，尝试为每个人找到一个符合条件的舞伴（即身高差不超过 `d`）。如果能够成功配对 `n` 对，则输出 `yes`，否则输出 `no`。 下面是具体的 C 程序实现： ```c #include <stdio.h> #include <stdlib.h> // 比较函数，用于 qsort 排序 int compare(const void *a, const void *b) { return (*(int *)a - *(int *)b); } int main() { int n, d; scanf("%d %d", &n, &d); int heights[2 * n]; for (int i = 0; i < 2 * n; i++) { scanf("%d", &heights[i]); } // 对身高进行排序 qsort(heights, 2 * n, sizeof(int), compare); // 尝试配对 int pairs = 0; for (int i = 0; i < 2 * n; i++) { if (pairs == n) { break; // 已经配对完成 } for (int j = i + 1; j < 2 * n; j++) { if (heights[j] - heights[i] <= d) { // 找到一个符合条件的舞伴 pairs++; // 标记已经配对的人 heights[j] = -1; break; } } } if (pairs == n) { printf("yes\n"); } else { printf("no\n"); } return 0; } ``` 解释 1. 输入读取：首先读取 `n` 和 `d`，然后读取 `2n` 个整数表示每个人的身高。 2. 排序：使用 `qsort` 函数对身高数组进行排序。 3. 配对： - 初始化配对计数器 `pairs` 为 0。 - 遍历排序后的身高数组，对于每个身高 `heights[i]`，尝试找到一个符合条件的舞伴 `heights[j]`（即 `heights[j] - heights[i] <= d`）。 - 如果找到符合条件的舞伴，增加配对计数器 `pairs`，并将 `heights[j]` 标记为已配对（设置为 -1）。 4. 输出结果：如果最终配对计数器 `pairs` 等于 `n`，则输出 `yes`，否则输出 `no`。 这个算法的时间复杂度主要由排序决定，为 \(O(2n \log 2n)\)，在给定的输入范围内是高效的。 ######[AI写代码神器 | 657点数解答 | 2024-10-24 18:45:51]