狗熊岭美人松查询问题的 C++ 实现

为了解决狗熊岭美人松查询问题，需要在给定的美人松高度数组中进行二分查找，以此判断每次询问的高度是否存在。下面是使用 C++ 编写的代码来解决这个问题： ```cpp #include <iostream> #include <cstdio> // 二分查找函数，用于查找高度为 target 的树是否存在 bool binarySearch(long long arr[], int n, long long target) { int left = 0, right = n - 1; while (left <= right) { int mid = left + (right - left) / 2; if (arr[mid] == target) { return true; } else if (arr[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return false; } int main() { int n, m; // 使用 scanf 读入 N 和 M scanf("%d %d", &n, &m); long long trees[1000001]; // 读入 N 棵美人松的高度 for (int i = 0; i < n; i++) { scanf("%lld", &trees[i]); } long long queries[1001]; // 读入 M 个询问 for (int i = 0; i < m; i++) { scanf("%lld", &queries[i]); } // 处理每个询问 for (int i = 0; i < m; i++) { if (binarySearch(trees, n, queries[i])) { printf("1"); } else { printf("0"); } if (i < m - 1) { printf(" "); } } printf("\n"); return 0; } ``` ### 代码解释： 1. **`binarySearch` 函数**：用于在数组 `arr` 中查找高度为 `target` 的树是否存在。采用二分查找算法，将查找范围不断缩小一半，直到找到目标元素或确定目标元素不存在。 2. **`main` 函数**： - 首先使用 `scanf` 读入 `N` 和 `M`，分别表示美人松的数量和询问的次数。 - 接着读入 `N` 棵美人松的高度，存储在数组 `trees` 中。 - 然后读入 `M` 个询问，存储在数组 `queries` 中。 - 对于每个询问，调用 `binarySearch` 函数进行查找，并根据查找结果输出 `1` 或 `0`。 ### 复杂度分析： - **时间复杂度**：二分查找的时间复杂度为 $O(log N)$，对于每个询问都需要进行一次二分查找，因此总的时间复杂度为 $O(M log N)$。 - **空间复杂度**：主要使用了两个数组来存储美人松的高度和询问，因此空间复杂度为 $O(N + M)$。 ######[AI问答 | 725点数解答 | 2026-02-25 18:29:17]