狗熊岭美人松查询问题的 C++ 解决方案

以下是使用 C++ 解决该问题的代码： ```cpp #include <iostream> #include <cstdio> #include <algorithm> const int MAXN = 1e6 + 5; long long trees[MAXN]; // 二分查找函数，查找高度为 target 的树是否存在 bool binarySearch(int n, long long target) { int left = 0, right = n - 1; while (left <= right) { int mid = left + (right - left) / 2; if (trees[mid] == target) { return true; } else if (trees[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return false; } int main() { int n, m; // 读取 N 和 M scanf("%d %d", &n, &m); // 读取 N 棵美人松的高度 for (int i = 0; i < n; i++) { scanf("%lld", &trees[i]); } // 对美人松高度进行排序（虽然题目说已经排好序，但代码保持完整性） std::sort(trees, trees + n); // 处理 M 次询问 for (int i = 0; i < m; i++) { long long k; scanf("%lld", &k); if (binarySearch(n, k)) { printf("%d", 1); } else { printf("%d", 0); } if (i < m - 1) { printf(" "); } } printf("\n"); return 0; } ``` ### 代码解释： 1. **二分查找函数 `binarySearch`**：该函数用于在有序数组中查找目标值 `target` 是否存在。通过不断缩小查找范围，直到找到目标值或确定目标值不存在。 2. **主函数 `main`**： - 读取输入的 `N` 和 `M`，分别表示美人松的数量和询问的次数。 - 读取 `N` 棵美人松的高度，并存储在数组 `trees` 中。 - 对数组 `trees` 进行排序（虽然题目说已经排好序，但代码保持完整性）。 - 处理 `M` 次询问，每次询问调用 `binarySearch` 函数判断高度为 `k` 的美人松是否存在，并输出结果。 ### 复杂度分析： - **时间复杂度**：排序的时间复杂度为 $O(N log N)$，每次二分查找的时间复杂度为 $O(log N)$，共进行 $M$ 次询问，因此总的时间复杂度为 $O(N log N + M log N)$。 - **空间复杂度**：主要使用了一个长度为 $N$ 的数组来存储美人松的高度，因此空间复杂度为 $O(N)$。 ######[AI问答 | 706点数解答 | 2026-02-24 19:56:57]