P1009天气之子 普及- CSP-S组 模拟 标准IO 传统题 来源 TomAnderson 时间限制 1000ms 内存限制 256MB 通过/尝试次数 2238/7787 题目描述 在一个古老的部落里，有一个关于天气之子的试炼。 试炼将会给出连续 n n 天的天气情况。每种天气被一个正整数编号。相同的正整数表示同一种天气。 每一天前，接受天气之子试炼的成员们必须每天给出当天的天气预报。预报准确率最高的会成为部落的天气之子。 你想出了一个奇妙的预报方法： 第一天预报天气为 <天气类型1>。从第二天开始： 若前一天预报成功，预报的天气类型保持不变。 若预报失败，统计前面所有天中的最多的天气（多种天气都是最多时，预报其中该天气第一次出现最晚的天气种类），修改当天的预报为该天气。 你的任务是计算你的预报成功天数。 输入格式 第一行一个正整数 n n，表示一共有 n n 天进行天气预报。 接下来一行 n n 个正整数 a 1 . . . a n a 1 ​ ...a n ​ ，其中 a i a i ​ 表示第 i i 天的天气情况。相同的正整数表示

```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$ 是不同天气的种类数。 [2026-02-07 18:29:12 | AI问答 | 797点数解答]