帮我优化时间复杂度：#include<iostream> #include<algorithm> #include<string> #include<unordered_map> using namespace std; int main() { unordered_map<string, string>curses; string curse; while ((getline(cin, curse)) && (curse != "END")) { size_t pos = curse.find(']'); string name = curse.substr(1, pos - 1); string effect = curse.substr(pos + 2);//因为']'后面有一个空格 curses[name] = effect; } int N; cin >> N; getchar();//很重要，读取上一个换行符 for (int i = 0; i < N; i++) { string query; getline(cin, query); if (query[0]=='[') //输入的是诅咒名字 { size_t cinPos = query.find(']'); string cinNmae = query.substr(1, cinPos - 1); if (curses.count(cinNmae)) cout << curses[cinNmae] << endl; else cout << "silence" << endl; } else //输入的是诅咒效果 { bool flag = 0; for (auto it = curses.begin(); it != curses.end(); it++) { if (query.compare(it->second) == 0) { cout << it->first << endl; flag = 1; break; } } if(flag==0) cout << "silence" << endl; } } return 0; }

这段代码主要的时间复杂度在于查询操作，即输入的是诅咒效果时，需要遍历整个 `unordered_map` 来查找符合条件的诅咒名称。这个操作的时间复杂度是 $O(N)$，其中 $N$ 是 `unordered_map` 中元素的个数。 为了优化时间复杂度，我们可以考虑使用一个 `unordered_map<string, vector<string>>`，其中 `vector` 中存储的是具有相同诅咒效果的诅咒名称。这样，查询操作的时间复杂度就可以降为 $O(1)$，具体实现如下： ```cpp #include <iostream> #include <algorithm> #include <string> #include <vector> #include <unordered_map> using namespace std; int main() { unordered_map<string, vector<string>> curses_by_effect; string curse; while ((getline(cin, curse)) && (curse != "END")) { size_t pos = curse.find(']'); string name = curse.substr(1, pos - 1); string effect = curse.substr(pos + 2); curses_by_effect[effect].push_back(name); } int N; cin >> N; getchar(); for (int i = 0; i < N; i++) { string query; getline(cin, query); if (query[0] == '[') { size_t cinPos = query.find(']'); string cinNmae = query.substr(1, cinPos - 1); if (curses_by_effect.count(cinNmae)) { for (const auto& name : curses_by_effect[cinNmae]) { cout << name << endl; } } else { cout << "silence" << endl; } } else { if (curses_by_effect.count(query)) { for (const auto& name : curses_by_effect[query]) { cout << name << endl; } } else { cout << "silence" << endl; } } } return 0; } ``` 这样，查询操作的时间复杂度就降为了 $O(1)$，整个程序的时间复杂度为 $O(N+M)$，其中 $M$ 是 `unordered_map` 中元素的总数。