“天气之子”试炼：用代码破解天气预报成功天数之谜，复杂度分析揭秘！

```cpp #include <iostream> #include <vector> #include <unordered_map> // 找到前面所有天中最多的天气，多种天气都是最多时，返回该天气第一次出现最晚的天气种类 int mostFrequentWeather(const std::vector<int>& weather, int endDay) { std::unordered_map<int, int> count; std::unordered_map<int, int> firstAppear; int maxCount = 0; int mostFrequent = 0; for (int i = 0; i < endDay; ++i) { count[weather[i]]++; if (firstAppear.find(weather[i]) == firstAppear.end()) { firstAppear[weather[i]] = i; } if (count[weather[i]] > maxCount || (count[weather[i]] == maxCount && firstAppear[weather[i]] > firstAppear[mostFrequent])) { maxCount = count[weather[i]]; mostFrequent = weather[i]; } } return mostFrequent; } // 计算预报成功的天数 int calculateSuccessDays(const std::vector<int>& weather) { int n = weather.size(); int forecast = weather[0]; int success = 0; for (int i = 0; i < n; ++i) { if (forecast == weather[i]) { success++; } else { forecast = mostFrequentWeather(weather, i + 1); } } return success; } int main() { int n; std::cin >> n; std::vector<int> weather(n); for (int i = 0; i < n; ++i) { std::cin >> weather[i]; } int result = calculateSuccessDays(weather); std::cout << result << std::endl; return 0; } ``` 代码解释 1. `mostFrequentWeather`函数： - 该函数接收一个存储天气情况的向量`weather`和一个表示天数的整数`endDay`。 - 它使用两个`unordered_map`：`count`用于记录每种天气出现的次数，`firstAppear`用于记录每种天气第一次出现的位置。 - 遍历前面所有天的天气情况，更新`count`和`firstAppear`。找出出现次数最多且第一次出现最晚的天气种类。 2. `calculateSuccessDays`函数： - 该函数接收一个存储天气情况的向量`weather`。 - 首先将第一天的预报天气设为第一天的实际天气。 - 遍历每一天，如果预报天气和实际天气相同，成功天数加1；否则，调用`mostFrequentWeather`函数更新预报天气。 3. `main`函数： - 读取输入的天数`n`和每天的天气情况，并存储在向量`weather`中。 - 调用`calculateSuccessDays`函数计算预报成功的天数，并输出结果。 复杂度分析 - 时间复杂度：对于每一天，计算前面所有天中最多的天气需要 $O(n)$ 的时间，因此总的时间复杂度为 $O(n^2)$。 - 空间复杂度：使用了两个`unordered_map`来记录天气出现的次数和第一次出现的位置，空间复杂度为 $O(m)$，其中 $m$ 是不同天气的种类数。 ######[AI问答 | 797点数解答 | 2026-02-07 18:29:12]