过年期间光头强应对美人松查询问题的C++代码实现

以下是解决该问题的C++代码： ```cpp #include <iostream> #include <unordered_map> using namespace std; int main() { int N, M; // 输入美人松的数量N和询问次数M cin >> N >> M; // 使用unordered_map来存储每棵美人松高度及其出现的次数 unordered_map<long long, int> treeCount; // 输入N棵美人松的高度，并统计每种高度的数量 for (int i = 0; i < N; i++) { long long height; cin >> height; treeCount[height]++; } // 进行M次询问 for (int i = 0; i < M; i++) { long long k; cin >> k; // 输出高度为k的美人松的数量，如果不存在则输出0 if (i > 0) { cout << " "; } cout << treeCount[k]; } cout << endl; return 0; } ``` ### 代码解释： 1. **输入处理**：首先读取美人松的数量`N`和询问次数`M`。 2. **统计美人松高度**：使用`unordered_map`来存储每棵美人松的高度及其出现的次数。遍历输入的`N`棵美人松的高度，将每种高度的出现次数进行累加。 3. **进行询问**：读取`M`个询问，对于每个询问的高度`k`，直接从`unordered_map`中获取该高度的美人松的数量并输出。如果该高度不存在，则`unordered_map`会默认返回0。 ### 复杂度分析： - **时间复杂度**：统计美人松高度的时间复杂度为$O(N)$，进行`M`次询问的时间复杂度为$O(M)$，因此总的时间复杂度为$O(N + M)$。 - **空间复杂度**：使用了`unordered_map`来存储美人松的高度及其出现的次数，最坏情况下的空间复杂度为$O(N)$。 ######[AI问答 | 502点数解答 | 2026-02-25 12:18:03]